{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Obstacle Removal to Reach Corner"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #graph #array #matrix #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #图 #数组 #矩阵 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumObstacles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #到达角落需要移除障碍物的最小数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>grid</code> ，数组大小为 <code>m x n</code> 。每个单元格都是两个值之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0</code> 表示一个 <strong>空</strong> 单元格，</li>\n",
    "\t<li><code>1</code> 表示一个可以移除的 <strong>障碍物</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。</p>\n",
    "\n",
    "<p>现在你需要从左上角&nbsp;<code>(0, 0)</code> 移动到右下角 <code>(m - 1, n - 1)</code> ，返回需要移除的障碍物的 <strong>最小</strong> 数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/04/06/example1drawio-1.png\" style=\"width: 605px; height: 246px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1,1],[1,1,0],[1,1,0]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。\n",
    "可以证明我们至少需要移除两个障碍物，所以返回 2 。\n",
    "注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/04/06/example1drawio.png\" style=\"width: 405px; height: 246px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> <strong>或</strong> <code>1</code></li>\n",
    "\t<li><code>grid[0][0] == grid[m - 1][n - 1] == 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-obstacle-removal-to-reach-corner](https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-obstacle-removal-to-reach-corner](https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,1],[1,1,0],[1,1,0]]', '[[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        r,c = len(grid),len(grid[0])\n",
    "        dist = [float('inf')] * (r*c)\n",
    "        dist[0] = 0\n",
    "        # visited = set()\n",
    "        queue = deque([(0,0)])\n",
    "\n",
    "        while queue:\n",
    "            x,y = queue.popleft()\n",
    "            # if (x,y) in visited:\n",
    "                # continue\n",
    "            # visited.add((x,y))\n",
    "            cur_pos = x*c+y\n",
    "            dx = [1,-1,0,0]\n",
    "            dy = [0,0,1,-1]\n",
    "            for i in range(4):\n",
    "                nx,ny = x+dx[i],y+dy[i]\n",
    "                n_pos = nx*c+ny\n",
    "                if 0<=nx<r and 0<=ny<c:\n",
    "                    new_dist = dist[cur_pos] + \\\n",
    "                        (0 if grid[nx][ny]==0 else 1)\n",
    "                    if new_dist<dist[n_pos]:\n",
    "                        dist[n_pos] = new_dist\n",
    "                        if grid[nx][ny] == 0:\n",
    "                            queue.appendleft((nx,ny))\n",
    "                        else:\n",
    "                            queue.append((nx,ny))\n",
    "            pass\n",
    "\n",
    "        return dist[r*c-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        visited[0][0] = True\n",
    "        queue = collections.deque()\n",
    "        queue.append((grid[0][0], 0, 0))\n",
    "        # queue = [(grid[0][0], 0, 0)]\n",
    "        while queue:\n",
    "            dist, i, j = queue.popleft()\n",
    "            for x, y in [(i-1,j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if 0<=x<m and 0<=y<n and not visited[x][y]:\n",
    "                    if x == m-1 and y == n-1:\n",
    "                        return dist + grid[-1][-1]\n",
    "                    visited[x][y] = True \n",
    "                    if grid[x][y]:\n",
    "                        queue.append((dist+grid[x][y], x, y))\n",
    "                    else:\n",
    "                        queue.appendleft((dist, x, y))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        directions = [-1,0,1,0,-1]\n",
    "        \n",
    "        n,m = len(grid),len(grid[0])\n",
    "        dis = [inf]*n*m\n",
    "        dis[0] = 0\n",
    "        q = deque([(0,0)])\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            if x==n-1 and y==m-1:\n",
    "                return dis[x*m+y]\n",
    "            for i in range(4):\n",
    "                xx = x + directions[i]\n",
    "                yy = y + directions[i+1]\n",
    "                if 0<=xx<n and 0<=yy<m and dis[xx*m+yy] > dis[x*m+y]+grid[x][y]:\n",
    "                    dis[xx*m+yy] = dis[x*m+y]+grid[x][y]\n",
    "                    if grid[xx][yy]:\n",
    "                        q.append((xx,yy))\n",
    "                    else:\n",
    "                        q.appendleft((xx,yy))\n",
    "        return dis[n*m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "联通：  BFS即可\n",
    "\n",
    "有墙，如何拆墙？-----》很像细菌感染\n",
    "\n",
    "将所有的 0保存起来，然后每个0进行扩展\n",
    "\n",
    "grid[0][0] == grid[m - 1][n - 1] == 0\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        lq,nq=[[0,0]],[]\n",
    "        rows=len(grid)\n",
    "        cols=len(grid[0])\n",
    "\n",
    "        visited=[[False]*cols for _ in range(rows)]\n",
    "        visited[0][0]=True\n",
    "        start_0_l=[[0,0]]\n",
    "\n",
    "        def bfs_get0(start_l):\n",
    "            nonlocal visited\n",
    "            start_0_l=start_l\n",
    "            lq,nq=start_l,[]\n",
    "            while(len(lq)):\n",
    "                for r,c in lq:\n",
    "                    for rr,cc in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                        nr=rr+r\n",
    "                        nc=c+cc\n",
    "                        if 0<=nr<rows and 0<=nc<cols:\n",
    "                            if not visited[nr][nc] and grid[nr][nc]==0:\n",
    "                                visited[nr][nc]=True\n",
    "                                nq.append([nr,nc])\n",
    "                start_0_l+=nq\n",
    "                lq,nq=nq,[]\n",
    "            return start_0_l\n",
    "\n",
    "        start_0_l=bfs_get0(start_0_l)\n",
    "        # print(start_0_l)\n",
    "        lq,nq=start_0_l,[]\n",
    "        ans=0\n",
    "\n",
    "        while(len(lq)):\n",
    "            for r,c in lq:\n",
    "                if r==rows-1 and c==cols-1:\n",
    "                    return ans\n",
    "                for rr,cc in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                    nr=rr+r\n",
    "                    nc=c+cc\n",
    "                    if 0<=nr<rows and 0<=nc<cols:\n",
    "                        if not visited[nr][nc] :\n",
    "                            grid[nr][nc]=0\n",
    "                            nq+=bfs_get0([[nr,nc]])\n",
    "                            visited[nr][nc]=True\n",
    "                            # nq.append([nr,nc])\n",
    "            ans+=1\n",
    "            lq,nq=nq,[]\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    设经过障碍物点的代价是1，非障碍物点的代价是0，转为求从(0, 0) 移动到右下角 (m - 1, n - 1)的最短路径。\n",
    "    使用Dijkstra算法搜索最短路径。1、初始化每个点的路径估计值；2、for循环，每次从V中挑出估计值最小的点u，对从u点出发的所有边松弛，从V中移除点u。就结果来看此算法没问题，但是还是超时，O(m*n*())\n",
    "    flag[x][y] [0]:从(0,0)到(x,y)要移除的最小障碍物数，[1]:True表示从(x,y)点出发的便都已松弛，该点已从V中移除\n",
    "    \"\"\"\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        flag = [[False]*n for row in range(m)]  \n",
    "        st = SortedList({(0, 0, 0)}, key=(lambda x: -x[0]))\n",
    "        flag[0][0] = True       \n",
    "        while st:\n",
    "            v,x,y = st.pop()\n",
    "            if x==m-1 and y==n-1:\n",
    "                return v\n",
    "\n",
    "            if x - 1 >= 0 and flag[x - 1][y] is False:\n",
    "                flag[x - 1][y] =True\n",
    "                st.add((v + grid[x-1][y], x - 1, y))\n",
    "            if y - 1 >= 0 and flag[x][y - 1] is False:\n",
    "                flag[x][y - 1]=True\n",
    "                st.add((v + grid[x][y-1], x, y - 1))\n",
    "            if y + 1 < n and flag[x][y + 1] is False:\n",
    "                flag[x][y + 1] =True\n",
    "                st.add((v + grid[x][y+1], x, y + 1))\n",
    "            if x + 1 < m and flag[x + 1][y] is False:\n",
    "                flag[x + 1][y] =True\n",
    "                st.add((v + grid[x+1][y], x+1, y))\n",
    "\n",
    "            \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        que = deque()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[0 for j in range(n)] for i in range(m)]\n",
    "        que.append((0,0,0))\n",
    "        path = [0,1,0,-1,0]\n",
    "        step = 0\n",
    "        while que:\n",
    "            while True:\n",
    "                r = que.popleft()\n",
    "                if r[-1] > step:\n",
    "                    que.appendleft(r)\n",
    "                    break\n",
    "                for i in range(4):\n",
    "                    x = r[0] + path[i]\n",
    "                    y = r[1] + path[i+1]\n",
    "                    if x >= 0 and x < m and y >= 0 and y < n and not vis[x][y]:\n",
    "                        vis[x][y] = 1\n",
    "                        if grid[x][y]:\n",
    "                            que.append((x,y,step+1))\n",
    "                        else:\n",
    "                            que.appendleft((x,y,step))\n",
    "                    if x==m-1 and y==n-1:\n",
    "                        return step+1 if grid[x][y] else step\n",
    "            step += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        # BFS - 使用双端队列\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        used = [[0 for _ in range(cols)] for _ in range(rows)]\n",
    "        my_queue = deque([])\n",
    "        my_queue.append((0, 0))\n",
    "        start_idx = 0\n",
    "        end_idx = 1\n",
    "        used[0][0] = 1\n",
    "        depth = 0\n",
    "        while start_idx != end_idx:\n",
    "            # number用于记录当前层的节点数\n",
    "            number = end_idx - start_idx\n",
    "\n",
    "            while number > 0:\n",
    "                this_i, this_j = my_queue.popleft()\n",
    "                start_idx += 1\n",
    "                number -= 1\n",
    "\n",
    "                if this_i == rows - 1 and this_j == cols - 1:\n",
    "                    return depth\n",
    "                # 上\n",
    "                if this_i-1 >= 0 and used[this_i-1][this_j]==0:\n",
    "                    if grid[this_i-1][this_j] == 0:\n",
    "                        my_queue.appendleft((this_i-1, this_j))\n",
    "                        start_idx -= 1\n",
    "                        number += 1\n",
    "                    else:\n",
    "                        my_queue.append((this_i-1, this_j))\n",
    "                        end_idx += 1\n",
    "                    used[this_i-1][this_j] = 1\n",
    "                # 下\n",
    "                if this_i+1 < rows and used[this_i+1][this_j]==0:\n",
    "                    if grid[this_i+1][this_j] == 0:\n",
    "                        my_queue.appendleft((this_i+1, this_j))\n",
    "                        start_idx -= 1\n",
    "                        number += 1\n",
    "                    else:\n",
    "                        my_queue.append((this_i+1, this_j))\n",
    "                        end_idx += 1\n",
    "                    used[this_i+1][this_j] = 1\n",
    "                # 左\n",
    "                if this_j-1 >= 0 and used[this_i][this_j-1]==0:\n",
    "                    if grid[this_i][this_j-1] == 0:\n",
    "                        my_queue.appendleft((this_i, this_j-1))\n",
    "                        start_idx -= 1\n",
    "                        number += 1\n",
    "                    else:\n",
    "                        my_queue.append((this_i, this_j-1))\n",
    "                        end_idx += 1\n",
    "                    used[this_i][this_j-1] = 1\n",
    "                # 右\n",
    "                if this_j+1 < cols and used[this_i][this_j+1]==0:\n",
    "                    if grid[this_i][this_j+1] == 0:\n",
    "                        my_queue.appendleft((this_i, this_j+1))\n",
    "                        start_idx -= 1\n",
    "                        number += 1\n",
    "                    else:\n",
    "                        my_queue.append((this_i, this_j+1))\n",
    "                        end_idx += 1\n",
    "                    used[this_i][this_j+1] = 1\n",
    "            depth += 1\n",
    "        return depth\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[ 0 for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        # 当前层队列 如果不是墙就加入当前队列       \n",
    "        que = deque()\n",
    "        que.append((0,0))        \n",
    "                \n",
    "        block_num = grid[0][0]\n",
    "        visited[0][0] = 1\n",
    "        \n",
    "        # 下层队列 如果是墙就加入下层队列，用set是为了防止重复加入墙到下层队列\n",
    "        next_que = set()\n",
    "        while True:\n",
    "            for _ in range(len(que)):\n",
    "                x,y = que.pop()\n",
    "                                              \n",
    "                if x == m - 1 and y == n - 1:\n",
    "                    return block_num\n",
    "                                                                                            \n",
    "                if x > 0 and visited[x-1][y] == 0 and (x-1,y) not in next_que:\n",
    "                    if grid[x-1][y] == 0:\n",
    "                        visited[x-1][y] = 1\n",
    "                        que.appendleft((x-1,y))\n",
    "                    else:\n",
    "                        next_que.add((x-1,y))                         \n",
    "                \n",
    "                if x < m - 1 and visited[x+1][y] == 0 and (x+1,y) not in next_que:\n",
    "                    if grid[x+1][y] == 0:\n",
    "                        visited[x+1][y] = 1\n",
    "                        que.appendleft((x+1,y))\n",
    "                    else:\n",
    "                        next_que.add((x+1,y))\n",
    "                \n",
    "                if y > 0 and visited[x][y-1] == 0 and (x,y-1) not in next_que:\n",
    "                    if grid[x][y-1] == 0:\n",
    "                        visited[x][y-1] = 1\n",
    "                        que.appendleft((x,y-1))\n",
    "                    else:\n",
    "                        next_que.add((x,y-1))   \n",
    "              \n",
    "                if y < n - 1 and visited[x][y+1] == 0 and (x,y+1) not in next_que:\n",
    "                    if grid[x][y+1] == 0:\n",
    "                        visited[x][y+1] = 1\n",
    "                        que.appendleft((x,y+1))\n",
    "                    else:\n",
    "                        next_que.add((x,y+1))\n",
    "            # 当前队列为空代表当前层已经遍历完，周围都是墙\n",
    "            if not que:\n",
    "                # 需要消灭的障碍物加一\n",
    "                block_num += 1 \n",
    "                # 下层队列升级为当然队列，继续搜索，直到能到右下角为止\n",
    "                for x,y in next_que:\n",
    "                    if visited[x][y] == 0:                       \n",
    "                        visited[x][y] = 1               \n",
    "                        que.append((x,y))\n",
    "                next_que = set()\n",
    "           \n",
    "              \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    设经过障碍物点的代价是1，非障碍物点的代价是0，转为求从(0, 0) 移动到右下角 (m - 1, n - 1)的最短路径。\n",
    "    使用Dijkstra算法搜索最短路径。1、初始化每个点的路径估计值；2、for循环，每次从V中挑出估计值最小的点u，对从u点出发的所有边松弛，从V中移除点u。就结果来看此算法没问题，但是还是超时，O(m*n*())\n",
    "    \"\"\"\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # dis[x][y] [0]:从(0,0)到(x,y)要移除的最小障碍物数，[1]:1表示从(x,y)点出发的便都已松弛，该点已从V中移除\n",
    "        dis = [[False for col in range(n)] for row in range(m)]\n",
    "        st = SortedList({(0, 0, 0)}, key=(lambda x: -x[0]))\n",
    "        c = 0\n",
    "        while st:\n",
    "            v,x,y = st.pop()\n",
    "            if x==m-1 and y==n-1:\n",
    "                return v\n",
    "            if dis[x][y]:\n",
    "                continue\n",
    "            c += 1\n",
    "            if x - 1 >= 0 and dis[x - 1][y] is False:\n",
    "                st.add((v + grid[x-1][y], x - 1, y))\n",
    "            if y - 1 >= 0 and dis[x][y - 1] is False:\n",
    "                st.add((v + grid[x][y-1], x, y - 1))\n",
    "            if y + 1 < n and dis[x][y + 1] is False:\n",
    "                st.add((v + grid[x][y+1], x, y + 1))\n",
    "            if x + 1 < m and dis[x + 1][y] is False:\n",
    "                st.add((v + grid[x+1][y], x+1, y))\n",
    "\n",
    "            # 松弛完从u出发的边，则将u打上标记(移除)\n",
    "            dis[x][y] = 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        ds = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "        q = deque()\n",
    "        used = set()\n",
    "        q.append([0, 0, 0])\n",
    "        while q:\n",
    "            x, y, cost = q.popleft()\n",
    "            if x * m + y in used:\n",
    "                continue\n",
    "            used.add(x * m + y)\n",
    "            if x == n - 1 and y == m - 1:\n",
    "                return cost\n",
    "            for d in ds:\n",
    "                nx = x + d[0]\n",
    "                ny = y + d[1]\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m or nx * m + ny in used:\n",
    "                    continue\n",
    "                if grid[nx][ny] == 1:\n",
    "                    q.append([nx, ny, cost + 1])\n",
    "                else:\n",
    "                    q.appendleft([nx, ny, cost])\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = [[10000000001] * n for i in range(m)]\n",
    "        res[0][0] = 0\n",
    "        cur = {(0, 0)}\n",
    "        while cur:\n",
    "            tmp = set()\n",
    "            for i, j in cur:\n",
    "                if (i, j) in tmp:\n",
    "                    continue\n",
    "                for k, l in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                    x, y = i + k, j + l\n",
    "                    if x >= 0 and x < m and y >= 0 and y < n:\n",
    "                        min_step = res[i][j] + grid[i][j]\n",
    "                        if min_step < res[x][y]:\n",
    "                            res[x][y] = min_step\n",
    "                            tmp.add((x, y))\n",
    "            cur = tmp\n",
    "        return res[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        dis=[[inf]*n for _ in range(m)]\n",
    "        dis[0][0]=0\n",
    "        q=deque([(0,0)])\n",
    "        while q:\n",
    "            x,y=q.popleft()\n",
    "            for nx,ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if 0<=nx<m and 0<=ny<n:\n",
    "                    g=grid[x][y]\n",
    "                    if dis[x][y]+g<dis[nx][ny]:\n",
    "                        dis[nx][ny]=dis[x][y]+g\n",
    "                        if g==0:q.appendleft((nx,ny))\n",
    "                        else:q.append((nx,ny))\n",
    "        return dis[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dis = [[inf] * n for _ in range(m)]\n",
    "        dis[0][0] = 0\n",
    "        q = deque([(0, 0)])\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    g = grid[x][y]\n",
    "                    if dis[x][y] + g < dis[nx][ny]:\n",
    "                        dis[nx][ny] = dis[x][y] + g\n",
    "                        if g == 0: q.appendleft((nx, ny))\n",
    "                        else: q.append((nx, ny))\n",
    "        return dis[m - 1][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        def bfs(x, y):\n",
    "            queue = deque([(x, y, 0)])\n",
    "            while queue:\n",
    "                xx, yy, level = queue.popleft()\n",
    "                for new_x, new_y in [(xx + 1, yy), (xx - 1, yy), (xx, yy + 1), (xx, yy - 1)]:\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and not visited[new_x][new_y]:\n",
    "                        visited[new_x][new_y] = True\n",
    "                        if grid[new_x][new_y] == 0:\n",
    "                            queue.appendleft((new_x, new_y, level))\n",
    "                        if grid[new_x][new_y] == 1:\n",
    "                            queue.append((new_x, new_y, level + 1))\n",
    "                        if new_x == m - 1 and new_y == n - 1:\n",
    "                            return level\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        return bfs(0, 0)\n",
    "\n",
    "\n",
    "grid = [[0, 1, 0, 0, 0],\n",
    "        [0, 1, 0, 1, 0],\n",
    "        [0, 0, 0, 1, 0]]\n",
    "Solution().minimumObstacles(grid=grid)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        q = [(0, 0, 0)]\n",
    "\n",
    "        while q:\n",
    "            cnt, x, y = heappop(q)\n",
    "            if (x, y) == (m-1, n-1):\n",
    "                return cnt\n",
    "            for dx, dy in delta:\n",
    "                i = x + dx\n",
    "                j = y + dy\n",
    "                if 0 <= i < m and 0 <= j < n and not visited[i][j]:\n",
    "                    visited[i][j] = 1\n",
    "                    \n",
    "                    heappush(q, (cnt + grid[i][j], i, j))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        col = len(grid[0])\n",
    "        row = len(grid)\n",
    "        dis = [[inf for i in range(col)] for j in range(row)]\n",
    "        dis[0][0] = 0\n",
    "        queue = deque()\n",
    "        queue.append((0,0))\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            for dx, dy  in ([-1,0], [0,-1], [1,0], [0,1]):\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if nx >= 0 and nx < row and ny >= 0 and ny < col:\n",
    "                    if dis[nx][ny] > dis[x][y] + grid[x][y]:\n",
    "                        dis[nx][ny] = dis[x][y] + grid[x][y]\n",
    "                        # 妙啊的代码\n",
    "                        if grid[x][y] == 0:\n",
    "                            queue.appendleft((nx,ny))\n",
    "                        else:\n",
    "                            queue.append((nx, ny))\n",
    "        return dis[row-1][col-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis =[[0] * n for _ in range(m)]\n",
    "        vis[0][0] = 1\n",
    "        q = deque([(0, 0)])\n",
    "        ret = 0\n",
    "        while True:\n",
    "            qnext = deque()\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if (x, y) == (m - 1, n - 1):\n",
    "                    return ret\n",
    "                for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:\n",
    "                        if grid[nx][ny] == 0:\n",
    "                            q.append((nx, ny))\n",
    "                        else:\n",
    "                            qnext.append((nx, ny))\n",
    "                        vis[nx][ny] = 1\n",
    "            q = qnext\n",
    "            ret += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        cost=[[m*n for _ in range(n)] for _ in range(m)]\n",
    "        # rec=[[0 for _ in range(n)] for _ in range(m)]#记录格子被遍历过的方向\n",
    "        q=deque()\n",
    "        di=[[-1,0],[1,0],[0,-1],[0,1]]#上下左右\n",
    "        #起点初始化\n",
    "        cost[0][0]=0\n",
    "        q.append((0,0))\n",
    "        # q.append((0,0,1))\n",
    "        # q.append((0,0,3))\n",
    "        # rec[0][0]=15\n",
    "        \n",
    "        while len(q)>0:\n",
    "            x,y=q.popleft()\n",
    "            for k in range(4):\n",
    "                nx,ny=x+di[k][0],y+di[k][1]\n",
    "                if -1<nx<m and -1<ny<n:\n",
    "                    if cost[nx][ny]>cost[x][y]+grid[nx][ny]:\n",
    "                        cost[nx][ny]=cost[x][y]+grid[nx][ny]\n",
    "                        q.append((nx,ny))\n",
    "        return cost[m-1][n-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        q = [(0,(0,0))]\n",
    "        vis = [[0] * n for i in range(m)]\n",
    "        while q:\n",
    "            v,(x,y) = heappop(q)\n",
    "            if vis[x][y] == 1:continue\n",
    "            vis[x][y] = 1\n",
    "            if x == m-1 and y == n-1:return v\n",
    "            for a,b in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if 0 <= a < m and 0 <= b < n and not vis[a][b]:\n",
    "                    heappush(q,(grid[a][b]+v,(a,b)))\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        # 狄杰斯特拉堆优化\n",
    "        queue = [[0,0,0]]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        end = [m-1,n-1]\n",
    "        inf = float('inf')\n",
    "        dis = [[inf for y in range(n)] for x in range(m)]\n",
    "        dis[0][0] = 0\n",
    "        while queue:\n",
    "            step,x,y = heappop(queue)\n",
    "            if step > dis[x][y]:\n",
    "                continue\n",
    "            if [x,y] == end:\n",
    "                return step\n",
    "            for i,j in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if not(0<=i<m and 0<=j<n):\n",
    "                    continue\n",
    "                if grid[i][j] + dis[x][y] < dis[i][j]:\n",
    "                    dis[i][j] = grid[i][j] + dis[x][y]\n",
    "                    heappush(queue,[grid[i][j] + dis[x][y],i,j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        q = list()\n",
    "        inf = 10**9\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        mark = [[inf] * col for _ in range(row)]\n",
    "        mark[0][0] = 0\n",
    "\n",
    "        q.append((0,0))\n",
    "        dic = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        while q:\n",
    "            x,y = q.pop()\n",
    "            \n",
    "            for i,j in dic:\n",
    "                nx = x+i\n",
    "                ny = y+j\n",
    "                if 0<=nx<row and 0<=ny<col and mark[x][y]+ grid[nx][ny] < mark[nx][ny]:\n",
    "                    mark[nx][ny] = mark[x][y]+ grid[nx][ny]\n",
    "                    q.insert(0,(nx,ny))\n",
    "        print(mark)\n",
    "        return mark[row-1][col-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        find=[[False for _ in range(n)]for _ in range(m)]\n",
    "        q=collections.deque()\n",
    "        d=[(-1,0),(0,-1),(0,1),(1,0)]\n",
    "        q.append((0,0,0))\n",
    "        while q:\n",
    "            a,b,dis=q.popleft()\n",
    "            if a==m-1 and b==n-1:\n",
    "                return dis\n",
    "            if find[a][b]:\n",
    "                continue\n",
    "            find[a][b]=True\n",
    "            for aa,bb in d:\n",
    "                aaa=aa+a\n",
    "                bbb=bb+b\n",
    "                if 0<=aaa<m and 0<=bbb<n:\n",
    "                    if find[aaa][bbb]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        if grid[aaa][bbb]==0:\n",
    "                            q.appendleft((aaa,bbb,dis))\n",
    "                        if grid[aaa][bbb]==1:\n",
    "                            q.append((aaa,bbb,dis+1))\n",
    "            \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = deque([(0,0)])\n",
    "        cost = [[inf] * n for _ in range(m)]\n",
    "        cost[0][0] = 0\n",
    "        while q:\n",
    "            i, j = q.pop()\n",
    "            for dx, dy in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n",
    "                x = i+dx\n",
    "                y = j+dy\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if cost[i][j] + grid[x][y] < cost[x][y]:\n",
    "                        cost[x][y] = cost[i][j] + grid[x][y]\n",
    "                        if grid[x][y] == 0:\n",
    "                            q.append((x, y))\n",
    "                        else:\n",
    "                            q.appendleft((x, y))\n",
    "        print(cost)\n",
    "        return cost[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dq = deque([(0, 0, 0)])\n",
    "        dis = [[inf]*n for _ in range(m)]\n",
    "        while dq:\n",
    "            d, i, j = dq.popleft()\n",
    "            if i==m-1 and j==n-1: return d\n",
    "            if dis[i][j] < d: continue\n",
    "            for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                ci, cj = i+di, j+dj\n",
    "                if ci < 0 or ci >= m or cj < 0 or cj >= n:\n",
    "                    continue\n",
    "                cd = d + grid[ci][cj]\n",
    "                if dis[ci][cj] <= cd: continue\n",
    "                dis[ci][cj] = cd\n",
    "                if grid[ci][cj]:\n",
    "                    dq.append((cd, ci, cj))\n",
    "                else:\n",
    "                    dq.appendleft((cd, ci, cj))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        Q = deque([(grid[0][0], 0, 0)])\n",
    "        while Q:\n",
    "            d,x,y = Q.popleft() \n",
    "            if vis[x][y]:\n",
    "                continue \n",
    "            vis[x][y] = 1\n",
    "            if x == m-1 and y == n-1:\n",
    "                return d \n",
    "            for nx, ny in [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]:\n",
    "                if 0<=nx<m and 0<=ny<n:\n",
    "                    if grid[nx][ny] == 0:\n",
    "                        Q.appendleft((d, nx,ny))\n",
    "                    else:\n",
    "                        Q.append((d+1, nx, ny))\n",
    "        return -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[1000000]*n for _ in range(m)]\n",
    "        dp[0][0] = 0\n",
    "        while True:\n",
    "            ok = True\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i-1>=0 and dp[i][j] > dp[i-1][j]+grid[i][j]:\n",
    "                        dp[i][j] = dp[i-1][j]+grid[i][j]\n",
    "                        ok = False\n",
    "                    if j-1>=0 and dp[i][j] > dp[i][j-1]+grid[i][j]:\n",
    "                        dp[i][j] = dp[i][j-1]+grid[i][j]\n",
    "                        ok = False\n",
    "            for i in range(m-1, -1, -1):\n",
    "                for j in range(n-1, -1, -1):\n",
    "                    if i+1 < m and dp[i][j] > dp[i+1][j]+grid[i][j]:\n",
    "                        dp[i][j] = dp[i+1][j]+grid[i][j]\n",
    "                        ok = False\n",
    "                    if j+1 < n and dp[i][j] > dp[i][j+1]+grid[i][j]:\n",
    "                        dp[i][j] = dp[i][j+1]+grid[i][j]\n",
    "                        ok = False\n",
    "            if ok:\n",
    "                break\n",
    "\n",
    "        return dp[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid):\n",
    "        move=[-1,0,1,0,-1]\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        distance=[[float(\"inf\")]* n for _ in range(m)]\n",
    "\n",
    "        deque=collections.deque()\n",
    "        deque.appendleft([0,0])\n",
    "        distance[0][0]=0\n",
    "\n",
    "        while deque:\n",
    "            x,y=deque.popleft()\n",
    "\n",
    "            if x==m -1 and y ==n-1:\n",
    "                return distance[x][y]\n",
    "\n",
    "            for i in range(4):\n",
    "                nx,ny=x+move[i],y+move[i+1]\n",
    "                if 0 <= nx < m and 0 <= ny < n and distance[x][y] + grid[nx][ny] < distance[nx][ny]:\n",
    "                    distance[nx][ny]=distance[x][y]+grid[nx][ny]\n",
    "                    \n",
    "                    if grid[nx][ny]==0:\n",
    "                        deque.appendleft([nx,ny])\n",
    "                    else:\n",
    "                        deque.append([nx,ny])\n",
    "                        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dis = [[inf] * n for _ in range(m)]\n",
    "        dis[0][0] = 0\n",
    "        q = deque([(0, 0)])\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    g = grid[x][y]\n",
    "                    if dis[x][y] + g < dis[nx][ny]:\n",
    "                        dis[nx][ny] = dis[x][y] + g\n",
    "                        if g == 0: q.appendleft((nx, ny))\n",
    "                        else: q.append((nx, ny))\n",
    "        return dis[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid):\n",
    "        move = [-1, 0, 1, 0, -1]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        distance = [[float('inf')] * n for _ in range(m)]\n",
    "\n",
    "        # 修正：将 deque 移到函数内部\n",
    "        deque = collections.deque()\n",
    "        deque.appendleft([0, 0])\n",
    "        distance[0][0] = 0\n",
    "\n",
    "        while deque:\n",
    "            x, y = deque.popleft()\n",
    "\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return distance[x][y]\n",
    "\n",
    "            for i in range(4):\n",
    "                nx, ny = x + move[i], y + move[i + 1]\n",
    "\n",
    "                if 0 <= nx < m and 0 <= ny < n and distance[x][y] + grid[nx][ny] < distance[nx][ny]:\n",
    "                    distance[nx][ny] = distance[x][y] + grid[nx][ny]\n",
    "\n",
    "                    if grid[nx][ny] == 0:\n",
    "                        deque.appendleft([nx, ny])\n",
    "                    else:\n",
    "                        deque.append([nx, ny])\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "from sortedcontainers import SortedList\r\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "# class Solution:\r\n",
    "#     def minimumObstacles(self, grid) -> int:\r\n",
    "#         m, n = len(grid), len(grid[0])\r\n",
    "#         # dis = [[float('inf')] * n for _ in range(m)]\r\n",
    "#         # dis[0][0] = 0\r\n",
    "#         if grid[0][0] == 0:\r\n",
    "#             q = [(0, 0, 0)]\r\n",
    "\r\n",
    "#         else:\r\n",
    "#             q = [(1, 0, 0)]\r\n",
    "\r\n",
    "#         vis = set()\r\n",
    "            \r\n",
    "#         while q:\r\n",
    "#             c, x, y = heapq.heappop(q)\r\n",
    "#             if (x, y) in vis:\r\n",
    "#                 continue\r\n",
    "#             vis.add((x, y))\r\n",
    "#             if x==m-1 and y==n-1:\r\n",
    "#                 return c\r\n",
    "#             for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\r\n",
    "#                 if 0 <= nx < m and 0 <= ny < n:\r\n",
    "#                     t = c + grid[nx][ny]\r\n",
    "#                     heapq.heappush(q, (t, nx, ny))\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumObstacles(self, grid) -> int:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        dist = [[float('inf')] * n for _ in range(m)]\r\n",
    "        dist[0][0] = 0\r\n",
    "        q = deque([(0, 0)])\r\n",
    "        while q:\r\n",
    "            x, y = q.popleft()\r\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\r\n",
    "                if 0 <= nx < m and 0 <= ny < n:\r\n",
    "                    if dist[nx][ny] > dist[x][y] + grid[nx][ny]:\r\n",
    "                        dist[nx][ny] = dist[x][y] + grid[nx][ny]\r\n",
    "                        q.append((nx, ny))\r\n",
    "        return dist[m - 1][n - 1]\r\n",
    "\r\n",
    "                    \r\n",
    "\r\n",
    "\r\n",
    "print(Solution().minimumObstacles(grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        distance=[[float(\"inf\") for _ in range(m)] for _ in range(n)]\n",
    "        \n",
    "        from collections import deque\n",
    "        queue=deque([(0,0)])\n",
    "        distance[0][0]=0\n",
    "        move=[-1,0,1,0,-1]\n",
    "        while queue:\n",
    "            x,y=queue.popleft()\n",
    "            if x==n-1 and y==m-1:\n",
    "                return distance[x][y]\n",
    "            for i in range(4):\n",
    "                nx=x+move[i]\n",
    "                ny=y+move[i+1]\n",
    "                if nx>=0 and nx<n and ny>=0 and ny<m and distance[x][y]+grid[nx][ny]<distance[nx][ny]:\n",
    "                    distance[nx][ny]=distance[x][y]+grid[nx][ny]\n",
    "                    if grid[nx][ny]==0:\n",
    "                        queue.appendleft((nx,ny))\n",
    "                    else:\n",
    "                        queue.append((nx,ny))\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        directions = [[0,-1],[0,1],[-1,0],[1,0]]\n",
    "        dist = [[float('inf') for _ in range(n)] for _ in range(m)]\n",
    "        queue =  deque([(0, 0, 0)])\n",
    "        dist[0][0] = 0\n",
    "        while queue:\n",
    "            x,y,cur_dist = queue.popleft()\n",
    "            if cur_dist > dist[x][y]:\n",
    "                continue\n",
    "            for r,c in directions:\n",
    "                r,c = r+x,c+y\n",
    "                if r < 0 or c < 0 or r >= m or c >= n: #越界\n",
    "                    continue\n",
    "                if cur_dist + grid[r][c] >= dist[r][c]: #距离没有缩小不入队\n",
    "                    continue\n",
    "                dist[r][c] = cur_dist + grid[r][c]\n",
    "                if grid[r][c] == 0:\n",
    "                    queue.appendleft((r,c,dist[r][c]))\n",
    "                else:\n",
    "                    queue.append((r,c,dist[r][c]))\n",
    "        return dist[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[inf for j in range(m)] for i in range(n)]\n",
    "        # dp[0] = grid[0]\n",
    "        pl = deque([(0,0)])\n",
    "        dp[0][0] = grid[0][0]\n",
    "        while pl:\n",
    "            i,j = pl.popleft()\n",
    "\n",
    "            for ni,nj in (i+1,j),(i,j+1),(i-1,j),(i,j-1):\n",
    "                if 0 <= ni < n and 0 <= nj < m and dp[ni][nj] == inf:\n",
    "                    dp[ni][nj] = dp[i][j] + grid[ni][nj]\n",
    "                    if grid[ni][nj] == 0:\n",
    "                        pl.appendleft((ni,nj))\n",
    "                    else:\n",
    "                        pl.append((ni,nj))\n",
    "                    if ni == n-1 and nj == m-1:\n",
    "                        break\n",
    "        \n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     for j in range(n):\n",
    "        #         if dp[i][j] =\n",
    "        return dp[n-1][m-1]\n",
    "\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # dis = [[inf] * n for _ in range(m)]\n",
    "        # dis[0][0] = 0\n",
    "        # q = deque([(0, 0)])\n",
    "        # while q:\n",
    "        #     x, y = q.popleft()\n",
    "        #     for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "        #         if 0 <= nx < m and 0 <= ny < n:\n",
    "        #             g = grid[x][y]\n",
    "        #             if dis[x][y] + g < dis[nx][ny]:\n",
    "        #                 dis[nx][ny] = dis[x][y] + g\n",
    "        #                 if g == 0: q.appendleft((nx, ny))\n",
    "        #                 else: q.append((nx, ny))\n",
    "        # return dis[m - 1][n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [float('inf')] * (m * n)\n",
    "        vis[0] = 0\n",
    "        best = set()\n",
    "        heap = [(0, 0, 0)]\n",
    "        while heap:\n",
    "            weight, i, j = heapq.heappop(heap)\n",
    "            if i*n+j in best:\n",
    "                continue\n",
    "            best.add(i*n+j)\n",
    "            for idx, pos in enumerate(((i+1,j), (i-1,j), (i,j+1), (i,j-1))):\n",
    "                x, y = pos\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    w = weight + (1 if grid[x][y] == 1 else 0)\n",
    "                    if x*n+y not in best and w < vis[x*n+y]:\n",
    "                        vis[x*n+y] = w\n",
    "                        heapq.heappush(heap, (w, x, y))\n",
    "        return vis[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        cost = [[inf] * n for _ in range(m)]\n",
    "        cost[0][0] = 0\n",
    "        q = deque()\n",
    "        q.append((0, 0))\n",
    "\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    g = grid[x][y]\n",
    "                    if cost[x][y] + g < cost[nx][ny]:\n",
    "                        cost[nx][ny] = cost[x][y] + g\n",
    "                        if g == 0:\n",
    "                            q.append((nx, ny))\n",
    "                        else:\n",
    "                            q.append((nx, ny))\n",
    "\n",
    "        print(cost)\n",
    "\n",
    "        return cost[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        dirs= [(0,-1),(0,1),(1,0),(-1,0)]\n",
    "        q = [(grid[0][0],0,0)]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        vis={}\n",
    "        while len(q):\n",
    "            [d,y,x] = heapq.heappop(q)\n",
    "            if y == m-1 and x == n-1:\n",
    "                return d\n",
    "            for dy,dx in dirs:\n",
    "                ny,nx = dy+y, dx+x\n",
    "                if 0<=ny <m and 0<=nx <n and (ny,nx) not in vis:\n",
    "                    vis[(ny,nx)] = True\n",
    "                    heapq.heappush(q,(d+grid[ny][nx],ny,nx))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = set((0, 0))\n",
    "        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        while q:\n",
    "            s, x, y = heappop(q)\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return s\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n:\n",
    "                    continue\n",
    "                if (nx, ny) in vis:\n",
    "                    continue\n",
    "                heappush(q, (s + grid[nx][ny], nx, ny))\n",
    "                vis.add((nx, ny))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        move = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        target = (m - 1, n - 1)\n",
    "        visited = set([(0, 0)])\n",
    "        hq = [(0, 0, 0)]\n",
    "        while hq:\n",
    "            cost, ux, uy = heapq.heappop(hq)\n",
    "            for dx, dy in move:\n",
    "                vx, vy = ux + dx, uy + dy\n",
    "                if 0 <= vx < m and 0 <= vy < n and (vx, vy) not in visited:\n",
    "                    if (vx, vy) == target:\n",
    "                        return cost + grid[vx][vy]\n",
    "                    visited.add((vx, vy))\n",
    "                    heapq.heappush(hq, (cost + grid[vx][vy], vx, vy))\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        import heapq as hq\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        queue = []\n",
    "        hq.heappush(queue, (grid[0][0], 0, 0))\n",
    "        visited = set([(0, 0)])\n",
    "\n",
    "        while queue:\n",
    "            barrier, i, j = hq.heappop(queue)\n",
    "            if i == m-1 and j == n-1:\n",
    "                return barrier\n",
    "            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                nx, ny = i+dx, j+dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:\n",
    "                    hq.heappush(queue, (barrier+grid[nx][ny], nx, ny))\n",
    "                    visited.add((nx, ny))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        steps = 1 if grid[0][0] else 0\n",
    "        pq, visited = [(steps, 0, 0)], set([(0, 0)])\n",
    "        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        while pq:\n",
    "            step, r, c = heappop(pq)\n",
    "            if r == R - 1 and c == C - 1:\n",
    "                return step\n",
    "            for dr, dc in directions:\n",
    "                row, col = r + dr, c + dc\n",
    "                if 0 <= row < R and 0 <= col < C and (row, col) not in visited:\n",
    "                    visited.add((row, col))\n",
    "                    if grid[row][col]:\n",
    "                        heappush(pq, (step + 1, row, col))\n",
    "                    else:\n",
    "                        heappush(pq, (step, row, col))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = deque([(0, 0, 0)])\n",
    "        seen = set([(0, 0)])\n",
    "        while q:\n",
    "            x, y, dist = q.popleft()\n",
    "            if x == m-1 and y == n-1:\n",
    "                return dist\n",
    "            for a, b in [(x-1, y), (x+1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0 <= a < m and 0 <= b < n and (a, b) not in seen:\n",
    "                    if grid[a][b]:\n",
    "                        q.append((a, b, dist+1))\n",
    "                    else:\n",
    "                        q.appendleft((a, b, dist))\n",
    "                    seen.add((a, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        def _01bfs(st, ed):\n",
    "            vis = [[False] * m for _ in range(n)]\n",
    "            dist = [[inf] * m for _ in range(n)]\n",
    "            dq = deque([st])\n",
    "            dist[0][0] = 0\n",
    "            while dq:\n",
    "                x, y = dq.popleft()\n",
    "                if (x, y) == ed: return dist[x][y]\n",
    "                if vis[x][y]: continue\n",
    "                vis[x][y] = True\n",
    "                for dx, dy in zip(dir_x, dir_y):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n and 0 <= ny < m:\n",
    "                        d = dist[x][y] + grid[nx][ny]\n",
    "                        if dist[nx][ny] <= d: continue\n",
    "                        dist[nx][ny] = d\n",
    "                        if grid[nx][ny]:\n",
    "                            dq.append((nx, ny))\n",
    "                        else:\n",
    "                            dq.appendleft((nx, ny))\n",
    "            return -1\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dir_x, dir_y = (-1, 1, 0, 0), (0, 0, -1, 1)\n",
    "        return _01bfs((0, 0), (n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = deque([(0, 0, 0)])\n",
    "        vis = set()\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        while 1:\n",
    "            i, j, k = q.popleft()\n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return k\n",
    "            if (i,j) in vis:\n",
    "                continue\n",
    "            vis.add((i,j))\n",
    "            for t in range(1,len(dirs)):\n",
    "                x, y = i + dirs[t-1], j + dirs[t]\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if grid[x][y] == 0:\n",
    "                        q.appendleft((x, y, k))\n",
    "                    else:\n",
    "                        q.append((x, y, k + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        import heapq\n",
    "        start, end = (0, 0), (m-1, n-1)\n",
    "        allPos = [(grid[0][0], 0, 0)]\n",
    "        visited = set()\n",
    "        result = 1e6\n",
    "        while allPos:\n",
    "            dis, i, j = heapq.heappop(allPos)\n",
    "\n",
    "            if i == m-1 and j == n-1:\n",
    "                result = dis\n",
    "                break\n",
    "\n",
    "            if f'{i}_{j}' in visited:\n",
    "                continue\n",
    "            visited.add(f'{i}_{j}')\n",
    "\n",
    "            for dir in dirs:\n",
    "                nextR, nextC = i + dir[0], j + dir[1]\n",
    "                if nextR < 0 or nextR >= m or nextC < 0 or nextC >= n:\n",
    "                    continue\n",
    "                heapq.heappush(allPos, (dis+grid[nextR][nextC], nextR, nextC))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        #\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        queue=deque([(0,0,0)])\n",
    "        def getNeighbors(posx, posy):\n",
    "            if posx:\n",
    "                yield (posx-1, posy)\n",
    "            if posy:\n",
    "                yield (posx, posy-1)\n",
    "            if posx < m-1:\n",
    "                yield (posx+1, posy)\n",
    "            if posy < n-1:\n",
    "                yield (posx, posy+1)\n",
    "        queue=[(0,0,0)]\n",
    "        vis={(0,0):0}\n",
    "        while queue:\n",
    "            c,x,y=heapq.heappop(queue)\n",
    "            for nx,ny in getNeighbors(x,y):\n",
    "                nc=c \n",
    "                if grid[nx][ny]==1:nc+=1\n",
    "                if (nx,ny) not in vis or vis[(nx,ny)]>nc:\n",
    "                    vis[(nx,ny)]=nc\n",
    "                    heapq.heappush(queue,(nc,nx,ny))\n",
    "        return vis[(m-1,n-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        q=queue.PriorityQueue()\n",
    "        q.put((0,0,0))\n",
    "        d=dict()\n",
    "        d[(0,0)]=0 \n",
    "        while(True):\n",
    "            cnt,x,y=q.get()\n",
    "            for p in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:\n",
    "                px,py=p[0],p[1]\n",
    "                if px>=0 and px<m and py>=0 and py<n:\n",
    "                    nl=cnt+grid[px][py]\n",
    "                    if (px,py) not in d or d[(px,py)]>nl:\n",
    "                        d[(px,py)]=nl\n",
    "                        q.put((nl,px,py))\n",
    "            if q.qsize()==0:break\n",
    "        return d[(m-1,n-1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        h = []\n",
    "        dic = {}\n",
    "        heappush(h, (0, 0, 0))\n",
    "        while 1:\n",
    "            (a, x, y) = heappop(h)\n",
    "            for d in [(-1,0),(0,-1),(1,0),(0,1)]:\n",
    "                nx, ny = x + d[0], y + d[1]\n",
    "                if nx < 0 or nx >= m or ny < 0  or ny >= n or (nx, ny) in dic:\n",
    "                    continue\n",
    "                res = a + (grid[nx][ny] == 1)\n",
    "                if nx == m-1 and ny == n-1:\n",
    "                    return res\n",
    "                dic[(nx, ny)] = res\n",
    "                heappush(h, (res, nx, ny))\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # seen = set()\n",
    "        # dic = {(m-1, n-1): 0}\n",
    "        # def dfs(x, y):\n",
    "        #     if (x, y) in dic:\n",
    "        #         return dic[(x, y)]\n",
    "        #     res = 1e9\n",
    "        #     seen.add((x, y))\n",
    "        #     for d in [(-1,0),(0,-1),(1,0),(0,1)]:\n",
    "        #         nx, ny = x + d[0], y + d[1]\n",
    "        #         if nx < 0 or nx >= m or ny < 0  or ny >= n or (nx, ny) in seen:\n",
    "        #             continue\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        vis=set()\n",
    "        q=deque()\n",
    "        q.append((0,0,0))\n",
    "        while q:\n",
    "            i,j,c=q.popleft()\n",
    "            if (i,j)==(m-1,n-1):return c\n",
    "            if (i,j) in vis:continue\n",
    "            vis.add((i,j))\n",
    "            for (ni, nj) in [(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)]:\n",
    "                if ni>-1 and ni<m and nj>-1 and nj<n:\n",
    "                    if grid[ni][nj]==1:\n",
    "                        q.append((ni,nj,c+1))\n",
    "                    else:\n",
    "                        q.appendleft((ni,nj,c))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "from sortedcontainers import SortedList\r\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumObstacles(self, grid) -> int:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        # dis = [[float('inf')] * n for _ in range(m)]\r\n",
    "        # dis[0][0] = 0\r\n",
    "        if grid[0][0] == 0:\r\n",
    "            q = [(0, 0, 0)]\r\n",
    "\r\n",
    "        else:\r\n",
    "            q = [(1, 0, 0)]\r\n",
    "\r\n",
    "        vis = set()\r\n",
    "            \r\n",
    "        while q:\r\n",
    "            c, x, y = heapq.heappop(q)\r\n",
    "            if (x,y) in vis:\r\n",
    "                continue\r\n",
    "            vis.add((x, y))\r\n",
    "            if x==m-1 and y==n-1:\r\n",
    "                return c\r\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\r\n",
    "                if 0 <= nx < m and 0 <= ny < n:\r\n",
    "                    t = c + grid[nx][ny]\r\n",
    "                    heapq.heappush(q, (t, nx, ny))\r\n",
    "                    \r\n",
    "\r\n",
    "\r\n",
    "print(Solution().minimumObstacles(grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "from sortedcontainers import SortedList\r\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minimumObstacles(self, grid) -> int:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        # dis = [[float('inf')] * n for _ in range(m)]\r\n",
    "        # dis[0][0] = 0\r\n",
    "        if grid[0][0] == 0:\r\n",
    "            q = [(0, 0, 0)]\r\n",
    "\r\n",
    "        else:\r\n",
    "            q = [(1, 0, 0)]\r\n",
    "\r\n",
    "        vis = set()\r\n",
    "            \r\n",
    "        while q:\r\n",
    "            c, x, y = heapq.heappop(q)\r\n",
    "            if (x,y) in vis:\r\n",
    "                continue\r\n",
    "            vis.add((x, y))\r\n",
    "            if x==m-1 and y==n-1:\r\n",
    "                return c\r\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\r\n",
    "                if 0 <= nx < m and 0 <= ny < n:\r\n",
    "                    t = c + grid[nx][ny]\r\n",
    "                    heapq.heappush(q, (t, nx, ny))\r\n",
    "                    \r\n",
    "\r\n",
    "\r\n",
    "print(Solution().minimumObstacles(grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        def _01bfs(st, ed):\n",
    "            v = 'JRBQ+RrRoBZxKZ+46OyFbiKVPnD8ADFL9tb5HAHkS4K5LQQgCnbp2gSmPCh4YEfpn6ToccaVJ8+Bu3Jo/r6IsVfy8m+2PSr8Hh4SU/gRlGxPNxDvBDJ5XkRTjlm+iI0ElAJAnTJve1fT08c5cfd8kHtvjZk00mAdeSo3urAAInzfO0vPH27A29dFd5cIHwXSdbPidAeeWCf/isOr2y4bqU6ywXIhS775d2b8a7izcEQbagsdQWcCPvcs7h0e1K500rPYGUoBACxKZf6m12TfJFW+9cbtIMrXvIRvgCepkewfM9nH+yxlcu/QhY73k+2FXseGaEKvaueXMHMS3Ez/Ii+HepOnACuULktYsTUoesOAVv9noKU14Yt+VCSgW6vFpab1nQ/3akF5m07Fz2xswRNYT5VxXjMbWQa1666pPab99SPOaKW6Xye2mLleuiAZpFbTjfN4s3OiMFJM7FQ6QuEmcd5aj/BZ9+SdcwupUGOCy05cKOmxDJ62aaQxUQEpcGs2pN95hxTKpY5qj48cZnds5CHd3UCE+GltcbCt0uxwg8cu1lWXacpVp5tibNfOat+E3TQ/oL4qan7stxAiUFIHedWIyv3RCjZZgZeE660rvuT2e7jkqBwYfkXDjVH8MdoVk/zijmW+kdF/QJbDZeimHvK3V8cGW4QQqXqGQmCXXC0c3NEeK7LWXD9Cjh436R1CvMMaxNczwM2b/u89oE4Jz1dSIrdMbL0QXIK7wmqql/TXxnW+i+xgtTs0Is0SQf3o/Y1Dy1EVKEkT4MJtBSOQWfBWRHyK0UFG7CZWL219AjkXWRF9kezml5cWHy8er3Mo1akZHI9Om+3yRHxf6tybe5giguTICfdDmMpRoxghQQqBxg6mHqDjm96kVocTvNVunmiKGIyqZqFyEedahtriBE0HyRm3I/jx6RC83TkfGjx061CFBasTkEijbExFAKIpKnA8gsySLZoCys7SO7yz3zvkASuIxjRupVNpnM5resC6Ne9T6rntpNiyrqogpikiTj1wCmfjMoUVMcwCCQj5q/lcQouoK27MyGnvX6tOIunO9RD6VVsVjF4SE5IuGVm47Hv4Leh9TVH7XOSXj3c3QOhpXS/dLh7AunByv9CXR0wrHEhL3jZpetywNnWcOwDAcNB/2NnjNl3oO3z3Uri5Oz9HNFohZ49RIIS3mctkg1ggk+IiCoP20wWGg5chM2k8w4p4iKvNBmka8juO15dYIXkp3+5rMWnAjDz0nzP/wTglB0bsODUtAKRRMs9t2FnpKthiwa3k+xVlRT9jiUpg1RLSIAMEBsdShWzfTVDjOQkskLXDstumuJVPTgV11eT+eJwxHtiuKJeYl8ZA6PDotCV/ry+fPZHUX5kNOriGHfcj/uaqsvwSqQFvzaZdJc6C84+4nX31YCVfPjapXtJFB0f3+apSoKgW923LiomSq8hwyhvJ7FclqD8P7DVEospu1fs2oR3/URnuRgIYIs0277WGQkO8g99OMSByRu9URfaAqLyvZEXmSCBSWBVvzqwA6wjGB/HT/B3IU9Ps67jblfWFRrBSPB88+RrlsQj7tzRfh9cVdB9CWxbnHqofPKTN3/7wrgBLhFjluZKuRsxi+XMzi6OYWcSyRg0IFUov7Lv56eZvUZG0n4X6MvmNoBMmjRP+chXfJm4FNKba3fNz1k8KyG428gGl5cofoPZ+oEbIsgtHWZeYE40UZzEBvsj3lUEr2gwhkF/f5fVLLmRYGjJTM7UORIeHAJCPzbcaUqMWJFkv088HjsNxXZp5S94fhY+4NhhL4B4iM/JJIQ/FqmXgqYXK77gvkfEAZnvS6a3W47s19MVM3jQ1lauutJkhq5Kilck+rXTSvJNT5Dyn7JfZsyKzor4s0czKg1ThyptNly6CcCRJw6J7NnbzBalgJHqf4mG6zN4CMaGm94DEQgB/5fUCZhP31fkp8i4owgDVM6QJAyqq4AWcxl+moFj2Rdzj6716mYtfVcOiEO1fa4eLhuMbvEV/1/ch+pk/0ks2bLcLPg3Tlol8wTvadyjEFQU42adHFTYOVZZZJnHjQ5t5A3ryzGXfV8lpIs6sfrdGN5mrWj8wx47Dk3hCKzmqFK2e4LS1WdAsc22RYhgzJk9LGibpEGkRYhvxy1Mi0XbbaBz2zj1t7ubGnVFat7EOGzPV/tO9/5mj/MTpqu3ZOuLzDE3S6PiKJz4f6oXj0bishLSGTuKglDLys1pCXxM5nvEaNQSrXOwhOCvNPxx25mvi5NiPs14RlK8JT0eHM4V8/PqbPG/j1OmlV6pXUuAAfDN741RXr0IqO236YzS4SmDfE0FZL/auPnAdEtgyLB102t9t4Wdcz0/o7daZSn/mv6Q0f8VlK8I2oARRCBGUUgEkkFYlh6JEDt8JOyK3mZcCKJdTpH1BWDjXrOTRY0pJMhLs4OcVrX8xGQvUv10i8W5yXYVOnuJ1MG901NsHxVCTX8VQscxa3Do/Rs9b1LxOcJp9auAdskiXlNJq+xuWNR3u4UbCUH+r2LDjBPcf45G8g1JwGqxKsEYOoQldUBXAFB024xgcgzXWzaVrIJ86SsPv3FwHr6zCczGdzZRdKTiuxBrrL3xP7DJP6g1msb/v8ZmAjgcLqcCbmJxna1Ap2CD6P42p6ZrCbaYWc/q/qwihblI5U+axhH/K7VO8M2sNEqZ/lKgLierxDRigrhhN1MxkEZDOcJTnbw9x0IcFTO564Dagcu02UENe9AkbntRHpGVP4Uebuv7Fh0nHVWq+wIUMZ2VqXQenrUi94Wtf+IyWRKZn+1138WIo9VP7WMQDMSZmgkYUOu1WmIUr8d1k5fXJgETLAcI1ssZSIL8oPFyzEv3HAx3T3LwdRXheuL03XUr/rlx7EuLj/8Xca4VaGogesfNoPrm7i8yLr0VbIHI5nx0FuwR2LjpQjefvGpnIiH3ar2fVxixH8BDTULESGVGMFNN9tAtS/JlnWjEzQJUla6LaSqfuJq9455X/f5APboxedftSwGt3mNcZomZ7ImaAkBxMUsHawnujpUc8vbZC3/oyMx5dMUvRaiMs9/7K4QrEnzal+9IyJfZ13BzaDiqcd47lwRIst6Umy6esogX0LsrLeWqPUf8Iy8EEamll3iCpT1/Bic5fUZPgZ7REjAPxyqPCHsMA3jWceXMKMAqFe67vd10xbeT5+KvDqLyEDNuCeEyW7eI2R4ycwb6u5HQSPMa10XrfDeotcrWwkfSVxygEs3d2eIXOF16+AaK/eJQbFBLP/f21TpZ3qFkQueNRaxvM0uRkDJjR4HvMioUMA20ssZQbTQWo67H4hY8yOYtwLt18Puo39hKzdvl5SOi58hyxBm9CpyJybQtNKqmU6Z/z4XY3/I/qLf1sPA2m0L/YdI//YGTIwuPZ6mAh8KSWm26IlpXTUQPVipepqzHAqzWqoLSZVddMVuRvamycEwtJiAowbsYl2jcnYLklBkJ39J4FgTjen+9nQf7z2ILgAzswm0ouwIWVdEzA0AVm5XiDs1msyN4tH2Xz7uKt5mtPqIL4ld1Eym0d5GAh9/g0F8037ZgjIsoOPQnVQmMpg14/0oHMEIaJ4L9vJG0GEhC5UGdtfSTFD/MjMDEbsVS3zO3ylmv1HgF2TKGAM9RpOPlatBlwt9XIiGoiFMJLPXM/NfsuAORyTDP5s9J7b8HXXx2lcI6xjuL71KusQZ0zneHAB1rFObODi/JZXbHWlzUULSKaqXCIdn+aodCQyVubDNkxEkiXWc+HujWl45kZTyEvaM30JtNb7vXfE0/JN3LWU2eS77a4jA+KYPHgZuG21JYhpIqudchmcmGcY2YHSM5ZrngIfew0XASXa8468Bja4SEBCddFsrz/uM5fHPSBV2tNWV2pqw3+hnubD+Iw24764ca/r1AAzUNi/dwI0pLlBcz6hVkKiWipYQx8qcaVP8WA/z1vd3V9rKq8sSxEcpv5SsYfp7atdGIq51OY281CFS7sXiBHa2NKK5Tu5J8TvEhyWrbF8PXrPN++kagpBTjAj8w2LN9Q5ptmOnaammyoQbRqxG95K/t2riUWGG6BVNIUvpOBpSe/2QZaCfj0Mq3vAMFQKE122d97acHDnpZny4hJeUjdSb402a9dgArUlih+FgS0i0AuD9dRHYtyDsRmxWMfBu2EW6B5jOR9GQcVxZuuN85WvWL8ocE28PPhQc+J6H0LkNk5uK60xguC8nI2WC1pVOe0mhPAVpl94WuQWQ3m5Q5u0X/yUo8w2Awl8VToIKa5lr9ejrtv6vHEP+pL2t5lNNoZivVCgTIOEz38S/cutHXdUlS1fB6HLNGd8lzm9QjJv5igrUdxSvcuyHf6dwwmny8830IQdta/UDiW0kLv0JCXG7eeopbr/XVORFkwfOZlNgbUXKR7qFdGv+PJzH8ajFd7zygkSuAjgc6dWTNqoV5Q2EMRMdbC8GnbhYRsLMJ7lGNkI18Cip5asJG0N/dgXBrzd6DbLw5uqQ+TWkwgp7cnjZ6ulVA116rA8CTzcAe5dG5jZmkamKppf0A/iQv0zupdjXZhXDtAKq5cih0382gJlB42E4FI0sEu1wUTguyN/fNeIo2CzKNjnZ6Fv74MRNcuwC6rU52VBBlw+MaX9krR58Mw0wLmRLJYSoBLFV8uvLFy5yf3xgyICPnHh9Rri6fi/1ikqCe/g2GKrw9eIgh6iIpok3QBEseS7SOIom56vz4ZL9Sd9rOAYD2Ivkgf9Hh8lBy4vBMyk8vXTBaSq9U1mRH0sD4oX+zReucVafrUG71o559lkAA5j4zcAYYpmmnC6FlMrOG831CMqffBllGOr+c6geoMQ6UaYBD9rEgk50qXDDWa9mSGk9j3WY5nKv98rDueeDEcIiyyDV/6y++umwlc1s1YZsQJUplaAxSaLLRYXVmoT13BWcs4vPRjLOxSWxKoU5l2LvaQTKoX389Ui17xXBeEdiNJ/S11QN1Yu99Gim+uD16nVgA1vQibmOmCG95JjqPfyjX5l0jt1wd9baI+3gPCJl3ffLlIiYx04c6U2xkrDWTOgMBcaIaVVGuPlpxcrc1oSK+puYrdL98yAFdin6OaN9DuMw8FhilzeEztjidT9tBOkTHvp184UZOcLljsEzbsTgQt1qYrFJaLtDMpN+UL0YnaOIvtdKAoAKpNgIo7VBbVFMMBAjDqXrFvKjAPuQAAp9KGaPzvGF6rGacb9YnhUfrNoFqVnY9RSecwTf74+nWVjIfGBU4T+OBUdTesH59W2BwUgZv6XT9I9u9HA1rgJPfRy3FTy7ZvqCWClri6DiJ1j28TE/ZEL/dMtmRTZckI8HdwteDv1jy2xoq4OTjkYv08XFEaePb4uBz9E7HeDNaeqgyM9oBAaP7jLPizeKd+gFfZcrQAeG3oTFWmkbh7OaGJ/P4LuMwTI9bL3b+y1ueYRbgECVzUiy39jR05iRKJBCStHjQVYSX6T+5S3cqHFf/9lJCYC4oe5aQcF4a19Nvg2URBJl8kvFGmB8wXu11M1CvoKEHsVP4TZ5mBdm6vMp9lGEWpR5B+yXAhPoGjGATltRO6E7o2f1w7n9HIkVM1mIAkp9k3ikcULx9fYjKrxcLDGum93HvFBdYZjv6A+Ccpsq4JI5XTePU0e8Z3ny/l7U/cS1eGCPjvhgvhAQwoNfODFjxpsqViK+cNjdYjcgKSOtlw8xhLkasO5+8MCeGqVtZOjnELw5FvrFUoxQM7QyDs33kTnnGzXa6XUg7mx84Oklwvw2ZicIulKTTLlO+MFZ10/Lpip2Xb9/RZ19HFCEpTNXoHW7l0elcyEgUvGi+ztEB2Hta/FEx7d80FqMGoZxEUtBGA7DUxRV0snReWqIsSwjRI4vyBS9/FzA99qeIhZZOIs0UPevlInBnHEQX1Jw8EKfoo0ZivnJDF906zucJsIFYR3pE/MmW9xiP0YERk9zWkmz2lpOkFdk4FHXIq0j4v7Ze+7hUJCqhtqQS+vTwTdWghWQiGOFKUCkGEpeqQ/dC4BJOOaS/8YLa8fLdfMQ6emvNgSjVINgAq9hdqbY0h2AGCKVLMb7q9gGwpQY2VyVHqcakzwZGxqCUSxMVYRj5MU2NqpWXgho2kGSe1gn9FXjLKVnxFbEWhBV3K'\n",
    "            vis = [[False] * m for _ in range(n)]\n",
    "            dist = [[inf] * m for _ in range(n)]\n",
    "            dq = deque([st])\n",
    "            dist[0][0] = 0\n",
    "            while dq:\n",
    "                x, y = dq.popleft()\n",
    "                if (x, y) == ed: return dist[x][y]\n",
    "                if vis[x][y]: continue\n",
    "                vis[x][y] = True\n",
    "                for dx, dy in zip(dir_x, dir_y):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n and 0 <= ny < m:\n",
    "                        d = dist[x][y] + grid[nx][ny]\n",
    "                        if dist[nx][ny] <= d: continue\n",
    "                        dist[nx][ny] = d\n",
    "                        if grid[nx][ny]:\n",
    "                            dq.append((nx, ny))\n",
    "                        else:\n",
    "                            dq.appendleft((nx, ny))\n",
    "            return -1\n",
    "        f = 'LI0eDiQLIT4QSCZLP3Ecoz+uefxvK5KQuj6578Vfg48XytKblfHwlE9NIvrxsqtkxkCA0RL3ZSGtVSfCkImc2ZxALGdQZVoY91FX5rx1ReXf4zvBxNLC9dcQ6iGiTixYtj0WYH21nkUWhT0UZYgvqQ4vrWmYiJw6Lg2d2ib/1ofbVljWq6HnuphyLouz6TzPO+OfTdsE2TfbOhGzpnGni+j+rPnT+J/jWjGuJ7qV9SCdzzTot56BJdzeiFmemKZ6gz467HR9tMmzwtTAhZAklgnxsdlbw5Lsy3nIKv2uYs/hmmKuv+QLJ3LvqmPBeHcAYOjFx5YIZVlKXbow4ys0mXsVVfweucY0l4FWUkuGYrPvTxINr45Lp4PiZQ7vgO6DEakdf/RfPmGzFf7vI/zIHOhMn6GOUWvrcOeDOh2wMQrXkqVdpAt9K9vpDxlmqd7W+9fXjsOsGZltb642uyqFxaOYA/C+uQd6qZxZ08YKqCgp62n5Ae8ZIf2wikoB1w8MWZ7iN0376GLyUOHAtzlz2yn9MoR5lqHtTLY/oRMfJGrUVSrjxy95L5KnTUmWt+0cpxQu2QNVrqhB2UzXgp+UNGB20gfFl5ZV2Hsx62FUpJIySTsjqJJttNW09sZUr3VBpjwAXvKr0rEjQNeI8+xEcGZiAjgnCZOX9GeJ8Z+qmM6Y+3MpkBjS8MKg589+M44GFi+in5OBSdkPjZ/TwVJ4ig0LEfaNqrZ8UiwD//BtM7N+5ssUjtRjg9out7Bys8cy5kGf5QUqoDDcfdkLpUP3PzH7+TceGPKCCjkaLoR8Kh5f3nxjJbrtU0MHqHyxZCaG3y+XmaOdQVOyJ6cDppOUNi3Q0A/3U/4P0zCQoB3xds6a7AI0awBvx8Cp5XZkJpTMfQ2Tbpzjlp87EnTXMcjM1dxHEAS2SLEX7HDFPkVSpR6N2BNjFZ0HBS/BflNy2ZZ+rFebVvvfD2MU4d5+dtOMf4UA9wQlYv914JLz4bTaysaEO6t3jbGstuCHy99Mhd8EXBIDe71F0z4W3B1EU8mkXNGr5/g3EYX/ug6/6yaMHGVWBo0W4gbZz3uSS2PWpnDr8spkoJRSUd9SyU9APWp68EOh//AzHdgzQPXOPMgSnYLn57lyCMBz9cpc1iz4MBHwQau5/XIWNIVML7RV8fGIotByPXdDLpnEGOe/UHhQYRMhc+stQYghAkKy9fo20Gev9amIgtZTVeiseuNqxLP2rICFgrwuAlbONqTOZ5UojFkkj6ynMvdawgi2FoBqR7MrhWyR54swFGNqzvJkbXgeeCyIVJfKCLJoBl+Gb6oGnahV01ejHPo/FcBUfl8JI3keiAaG1/+dyjrSP9YpEm6oev3VH7hbI/xOWDDG3p9EChHOf7SuloKaPvdUPeuJF+tuAzgkVRb5d85q+UZCDW7Wso2FBYYZ4OhFFkrpTPxboW99hTwIL/O9MP5QTwIA1QvPewOMFdqB9+5gvv6H67C5KqfBVCm6KijHkgAkboqvoTooZYvlSx+2lUQ8y3CyMvBEvTbGOo0wa+8L9fzdGCnqeunbOUbMba1Fx17GF09vo+KhnK5lfGycRnFUSQvCPDbG80DQcRC8LItkDqgBBNkjKSBKdJuye/0vRYjgw1jHx+iXYpSCgN1076Bp2QxbfPWCXB4fWLjRG9SclU86EnMbi9WcU+eYl5+8CjRk72j5NwcbX6ziETvb82mXrjfhjJsMJNWGH5wf7EkN4Myz8NLA6VVR01N3iXPoHymVeN+Tmp2D7xeMHczhXIvXVxAyMZXHxQRYfgbfJcIyy2SVPlgYALzEXDIKLiQjpPWM8lBJOqFmVPU9gtWBg8tezDfEzYN/Qrtkjc5usOl6KcTXwVPHWKK6HNIl2mMz61HkJScmBfigdj35SHD2meS1VQdpLHwn9/L870ZLJrSg4aPt6OLVjXA5uHo9UXEvRHtC846pXTRoOW1oF88oH/HRRrOut/Q1OhK+enpt1tcs6miY55IwMAvebBHsf9jPC2cPNOs22hX4ZOQj1O5KCLqrjgw4KQj8QCF45MLGqdxNmAnea6++ZQksQX8Ui1Q6QMUGSAuuKTBa3ZxKAWQGehlPfn6V56Z/ZKC3difFD8mQLI2oNmn8FNi8sE+M0tHIog94vdi7j/r353oImeoggy4p646bvr34FSxUi0aokxaL8x6olfalnYNYSiYJVElg18t8/hH98GNlpsRG8SfpFLW7Q7Ibje4L07RmDhD1O/oSTJQ8LiRBS/v8UwV7EXumn/SBM9dLlnOWoe+WjoEohRe9D5VcEtQi/DPC0gPXNvKr/DrYqe6aqCixc1f/CAPlCkVmCI4+Iw/5NT/K+Rq9P5A/F2iQY7D8CDp1GktCMsI55oTXJrIm3afQ+hkjVyExl61T4yWefXNLeNM33Y2lnJKyfgZ2T60tPQenir2WKJvGtq9SuIBtTFHdq2VFuXdCvU+QvwuN9IcrpDZWU5hQ28aDdV3Dk1Cs0H0NAQ3TRTcqt+z2L+eKRNZc/qzCJAbFqU5uj1jLO7S015TtjOdED0c9Hxn6Y8igPCvbicr0kJBaR9RY+xs8UAkTNqvjUT9UVBq28VC4aE5C/bfmUcfniHj4ZA5hUt9dRMiWCZp34NNesNtzurk+JNi+CTZBUgQHIoSWScpyUoaHaKob7kRQdDIAR/63o9amSAtQ8tqSvZYJFnP8S+Eb9Dmq1tyV86nMvvMZoiHClmKWv42OzscHSyLFGAvJXjICWtCGpHff/mP4qT0SYNV3UjNButkTn/TXqoEdFcEV5vHM2YM1oJI5ZSxOSFQUlKCg998gl1Q1nfb0xfPkqnx7UWXuQUq+YyzrJLPNBm1s7yDoayjrKuyWZ/228ZIUXHjWAk1lYL9o1n+hIxdkM3YbuHnFWMHJyn/DVnJ3LUhRRDctkBOdNbOk8MLE6IdJylK+i+3RsEFUIWplVpaXJzokGeUiBrZVfPOSz/CZpaoC1t/IsbsCHsJNaywRXsDEQqtoV+DHRhWB5CrxhnzTlO0ymQp+rt1K1wDF/mIHDeB5zZwB25Ftme31G3aq4qOEsptK7ROIk19QDzxqX7xI4RD9fSY9HKBk43OZsZbEAGDqIH+YV5+qbAZucoQYeRtx5Iy+n8HYM9ZD1JTwejugFZHkIncm8jsVit57XvnZ0+TIe+OcETZoPP5kbU19vVGvyJcrWy21mDkySO36NuR6HFo9ICKcjan51XR18wIunSUVKyy2DG1CU+9SD+gC3/gvIIovb/s6g0AnGQRcdk3SWhMHuNFK5LWGPi0sxCpxpyQpYufolHQGmBqX03jlkAPU8xU1BBUZ/LcHBPb8kd+x7hdzdEx1dmAoHKcDtgeGCsee5hPd8YOzq5pndq9L3MbYROKfkI4BZ165r3tapBkaSGpbua34xLcTg7QtDwNdC3Cjgn893GEGS27syUZIWL7kITm1OqngmE1SXU7p6SE00hua5TVDvW35rG/G9M2f2sSYGQh2KSGCBxRbGk/rF3F60bKi1dXknekLr98e05MojcVUDXnt0aWAi50YIuNaQ6ueadG+ovZQNzgIQUKe7+aQWIf6UUoyidI7fAt1Ac51OjeNiSacI78rocXeqPJctL/bKwryR6d766IOW7QmVbKOFKpDqGgBDPXZ3xoo8HiSxqiD0nFL4o6VpabL1s/vpIP9DNEU9dKH1hm18DhvL/c8FUds5fgVcCrjCtC6QjmpRhK/ygVxsfT8qDQhhDP237Bfnz5HB41w/QQh5fl4RMyOjc21LN7OkrTCYjDn7M4+pYjzlU/74C5QaXt1Bh7tuL6xBHx18cc6KCw+cjuJVJYflmii9NN7GZNTTCTwue2K8g7e/LPEnZ3SFeHqBCzhxOsKUlVvx2XZPu038Ajxnr3pyjQzpaTLbL2nBSp6L5fzGN//R/NWBFPpjX0WoYoor9IX321giAGdYoshbB2l5yYzZ/V08lzMHoAKZZ1vcxUMhB0ttA5/SWhMgP1AblOTbxRKewUydwzTVu1o8NYhl7LX/xjxil5JsIhqsdI7mIgWEP3vUuzVp18y72W4s2WuCX9neT74V4zsil8WcnMIyAOjieJjzcP06ne6WW7l1ZXkOdAsuQljqZSNCY0+4+Ce/isoIygE4WcqT1vSRk72c3iiG7vZ9TQs++A3kuQNjeycrfyyGuAB1KDLTBeLuGWkybd+72sgurzxECD8lr9F/EIaJ1MU162au78jHqOXf9k9OBHpNitTzMSTmxPCF4OXM3rg0exJUl4UULxmz4sXchC25uC04L3cfeFmnSBOqICSMBHAQVEZzU7VIOSfILubpAHSqdILOthpCM4eqqgH0NVa7RB/+HGGqw11BavOe755VIWkhjR4RpbDGaNsf0O64pDtkW/W3QZz4WSaT0f3AcJWvdjH4o2u9t8TIuyKy7tIb+CdSP/ZY7JBA8YccyuNYiTGIU5VTv6qQatu7LQTVwnwQ7z7+KWCNp3+xoBZRFxFR0qiihB3kleVfqF5PCQRCaZg2bqok5M/kKVby0EQ056hVYaNVIY6l2OjoucyRJbweokR9l98iJYIIPIl/nRLc9JS/fKsORKdSN/01O97J/xPytxTfE5iO5LXpGLdlLJpweVBGaIEIi0ApsDfaCWbHovi4rVPNvup09z8OfxjqKq4q3KLL03fB+J1hNyZczxYswLPHPH9syanN0/e7BFNrj7hltW2SapH0vMrVOAzuXhwWxyoF0OmzA8iLtZSCQ1fEn1FbOTQT46NYJs01MBDajFPLm9Ps26XhBLMD/dfj9Ibk+IlQqnxhcnGc0JNfh5FTHyxrvCHuEjM9bXAx47HcPzApzMtW2Z1vIrpZf3evUB/HMIMM+2vDagHOGb8VCDiP3+Cj9bOcedW6ZZbA8TvxPPJalZ6buj0oGpks/grYx6NMsW9NVDM8EsVSYKYg5mrATreV4VB5D0iTU+Nnu+M3f2B4IgrRtKbsoYcipnH4ALaWQA07yvRq30+C11e/KE6lCcGZlllfZ8incOmKY3YDZBbMdEHdJti1wqHqaodJ8a8Pzm2Wa7Mrrw4K2XWqJ1+Iyl53TZUeFdvwgxHMWkywotTe+h9W9eXx0Td51tv3vDdaTQkSauEjPVOOs7L4sPjjRYeuUkLBQsOwUXNX6f4BLUGXqusrGcN227wd1JatKTeEdAUNyYJ35YBXSZiWE09VLJVCCxKijeeWIMvc3UfNQmrzXhPAU9y8GDv30Mi/kcDDuWE7R5cR/Omcb51LJrXAoPiyXrcfspfc/KioSlL3x09kZ/OZnOIFKUHRKmV6gwI5GcJaK0UmqhC+QQvtDPQPyB4KbHG7sn6S1UoqPPuNXClS2AavrXcG5OJ7lgZpCPqfpOB8tGUtTEi2iNzL6hYWq3ggBskHVTFbGGOfSYyvZ5a3E/ITV/hVI+3CZxMLJ5b6eOhtvw8Ik9hZEaakjI5MtTLwBMDV9iC7UVZAyCVHQCn/WUkxmTRpFbXZT4qs5O1HVz31mtHJkg7pduLpOX4otc5aQav2KC0IDRHAe93KDpaug5xzCkVp0VhNmG4bRkYYBDu/MMy2Mj0ARy+yo/0xaUaNVZLCsFquzlEqhIuMP2VA6QlBT8rrUca4Za+KRatDfCfOmnd2LGijruhqZxL/6+IP8m8KFb5DKAeRXrNrTXVdINSzrbIhEE8e44yky0EveYS0/+ngXLizHNDCyEyZDz0NnRgySJOrhK82gVQ4uhTc/1ZAfD1QU2Spz4ubdJKPOaZKtHNV/PT2Kpz1YBO1vK6ViFL8gD10AakitO6sB2YKWFjKRLOhE5X59U0R8qk97fHVKaa/4x9ArSxm0mtzg+Vy0OahuyT1Ao804VoiFyjVpXH2uNNmTUbcRWtV+2To72EvUf2vA0BQQRwvJPA8AbjwOqXJAbigZUJtgvmbjthjxsJeP4gB8+113kPhf54saD/DTfWByINFeeiqnuzY5B/Fd9F9Sw47qzHEgdm/rzhK7RcWbLx4aujdQf6pZiVWiOsSdOkxAOX5k0XCR+E2XI3K90y0Iw2pSx7gHB5fxEp/V3E/RwepNXSjUBRSbchaaPsTFC8/eBHmMawoDbm78K3PGLLA4iTQv4Lb63kanbqiarHNBFzGJJp35UPM05Xc5hj'\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dir_x, dir_y = (-1, 1, 0, 0), (0, 0, -1, 1)\n",
    "        return _01bfs((0, 0), (n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        r,c = len(grid),len(grid[0])\n",
    "        dist = [float('inf')] * (r*c)\n",
    "        dist[0] = 0\n",
    "        visited = set()\n",
    "        queue = deque([(0,0)])\n",
    "\n",
    "        while queue:\n",
    "            x,y = queue.popleft()\n",
    "            if (x,y) in visited:\n",
    "                continue\n",
    "            visited.add((x,y))\n",
    "            cur_pos = x*c+y\n",
    "            dx = [1,-1,0,0]\n",
    "            dy = [0,0,1,-1]\n",
    "            for i in range(4):\n",
    "                nx,ny = x+dx[i],y+dy[i]\n",
    "                n_pos = nx*c+ny\n",
    "                if 0<=nx<r and 0<=ny<c:\n",
    "                    new_dist = dist[cur_pos] + \\\n",
    "                        (0 if grid[nx][ny]==0 else 1)\n",
    "                    if new_dist<dist[n_pos]:\n",
    "                        dist[n_pos] = new_dist\n",
    "                        if grid[nx][ny] == 0:\n",
    "                            queue.appendleft((nx,ny))\n",
    "                        else:\n",
    "                            queue.append((nx,ny))\n",
    "            pass\n",
    "\n",
    "        return dist[r*c-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        cost = [[1e9 for _ in range(n)] for _ in range(m)]\n",
    "        vis = [[False for _ in range(n)] for _ in range(m)]\n",
    "        cost[0][0] = 0\n",
    "        vis[0][0] = True\n",
    "        q = []\n",
    "        heapq.heappush(q, (0, 0, 0))\n",
    "        while q:\n",
    "            c, x, y = heapq.heappop(q)\n",
    "            order = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "            for a, b in order:\n",
    "                if 0 <= x + a < m and 0 <= y + b < n and not vis[x + a][y + b]:\n",
    "                    add = grid[x + a][y + b]\n",
    "                    vis[x + a][y + b] = True\n",
    "                    heapq.heappush(q, (c + add, x + a, y + b))\n",
    "                    cost[x + a][y + b] = c + add\n",
    "        return cost[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        count = [[float('inf')] * n for _ in range(m)]\n",
    "        q = [(0, 0, 0)]\n",
    "\n",
    "        while q:\n",
    "            cnt, x, y = heappop(q)\n",
    "            if (x, y) == (m-1, n-1):\n",
    "                return cnt\n",
    "            for dx, dy in delta:\n",
    "                i = x + dx\n",
    "                j = y + dy\n",
    "                if 0 <= i < m and 0 <= j < n and not visited[i][j]:\n",
    "                    visited[i][j] = 1\n",
    "                    if cnt + grid[i][j] < count[i][j]:\n",
    "                        count[i][j] = cnt + grid[i][j]\n",
    "                        heappush(q, (cnt + grid[i][j], i, j))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dis = [[inf] * n for _ in range(m)]\n",
    "        dis[0][0] = 0\n",
    "        q = deque([(0, 0)])\n",
    "        vis = [[False]*n for _ in range(m)]\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            if vis[x][y]:\n",
    "                continue\n",
    "            vis[x][y] = True\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    g = grid[x][y]\n",
    "                    if dis[x][y] + g < dis[nx][ny]:\n",
    "                        dis[nx][ny] = dis[x][y] + g\n",
    "                        if g == 0: q.appendleft((nx, ny))\n",
    "                        else: q.append((nx, ny))\n",
    "        return dis[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        distence = [[inf] * n for _ in range(m)]\n",
    "        distence[0][0] = 0\n",
    "        q = deque([])\n",
    "        q.append((0, 0))\n",
    "        vis = [[False]*n for _ in range(m)]\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            if vis[i][j]:\n",
    "                continue\n",
    "            vis[i][j] = True\n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return distence[i][j]\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                if 0 <= x < m and 0 <= y < n and distence[i][j] + grid[x][y] < distence[x][y]:\n",
    "                    distence[x][y] = distence[i][j] + grid[x][y]\n",
    "                    if grid[x][y] == 0:\n",
    "                        q.appendleft((x, y))\n",
    "                    else:\n",
    "                        q.append((x, y))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        dis = [[inf]*n for _ in range(m)]\n",
    "        vis = [[False]*n for _ in range(m)]\n",
    "        dis[0][0] = 0\n",
    "        vis[0][0]=True\n",
    "        q = [(0,(0,0))]\n",
    "\n",
    "        while q:\n",
    "            d,(x,y) = heappop(q)\n",
    "            # print(d,x,y)\n",
    "            vis[x][y] = True\n",
    "            if x==m-1 and y==n-1:\n",
    "                return d\n",
    "            for nx,ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if 0<=nx<m and 0<=ny<n and not vis[nx][ny]:\n",
    "                    nd = d+1 if grid[nx][ny] == 1 else d\n",
    "                    if nd < dis[nx][ny]:\n",
    "                        dis[nx][ny] = nd\n",
    "                        heappush(q,(nd,(nx,ny)))\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        def _01bfs(st, ed):\n",
    "            vis = [[False] * m for _ in range(n)]\n",
    "            dist = [[inf] * m for _ in range(n)]\n",
    "            dq = deque([st])\n",
    "            dist[0][0] = 0\n",
    "            while dq:\n",
    "                x, y = dq.popleft()\n",
    "                if (x, y) == ed: return dist[x][y]\n",
    "                if vis[x][y]: continue\n",
    "                vis[x][y] = True\n",
    "                for dx, dy in zip(dir_x, dir_y):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < n and 0 <= ny < m:\n",
    "                        d = dist[x][y] + grid[nx][ny]\n",
    "                        if dist[nx][ny] <= d: continue\n",
    "                        dist[nx][ny] = d\n",
    "                        if grid[nx][ny]:\n",
    "                            dq.append((nx, ny))\n",
    "                        else:\n",
    "                            dq.appendleft((nx, ny))\n",
    "            return -1\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dir_x, dir_y = (-1, 1, 0, 0), (0, 0, -1, 1)\n",
    "        return _01bfs((0, 0), (n - 1, m - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        ## bfs+双向队列\n",
    "        # dp[0][0] = 0\n",
    "        # q = deque()\n",
    "        # q.append((0, 0))\n",
    "        # # bfs 初始每个位置都是inf, 然后更新所有路径\n",
    "        # while q:\n",
    "        #     x, y = q.popleft()\n",
    "            \n",
    "        #     for nei in neighbors:\n",
    "        #         nextx = x + nei[0]\n",
    "        #         nexty = y + nei[1]\n",
    "        #         # 边界情况\n",
    "        #         if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:\n",
    "        #             continue\n",
    "        #         d = grid[nextx][nexty]\n",
    "        #         if dp[nextx][nexty] > dp[x][y] + d:\n",
    "        #             dp[nextx][nexty] = dp[x][y] + d\n",
    "        #             # 技巧 优先走短路\n",
    "        #             if d == 0:\n",
    "        #                 q.appendleft((nextx, nexty))\n",
    "        #             else:\n",
    "        #                 q.append((nextx, nexty))\n",
    "        # return dp[m-1][n-1]\n",
    "        ## dijkstra\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        minHeap = []\n",
    "        # 分别是距离,x, y 距离是第一位因为要以此维护最小堆\n",
    "        heapq.heappush(minHeap, (0, 0, 0))\n",
    "        dist[0][0] = 0\n",
    "        while minHeap:\n",
    "            d, x, y = heapq.heappop(minHeap)\n",
    "            if visited[x][y] == True:\n",
    "                continue\n",
    "            visited[x][y] = True\n",
    "            for nei in neighbors:\n",
    "                nextx = x + nei[0]\n",
    "                nexty = y + nei[1]\n",
    "                cost = grid[x][y]\n",
    "                if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:\n",
    "                    continue\n",
    "                # 更新最短路径\n",
    "                if dist[nextx][nexty] > dist[x][y] + cost:\n",
    "                    dist[nextx][nexty] = dist[x][y] + cost\n",
    "                    heapq.heappush(minHeap, (dist[nextx][nexty], nextx, nexty))\n",
    "        return dist[m-1][n-1]\n",
    "                \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        # first method\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = deque([])\n",
    "        seen = dict()\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        q.append((0, 0, 0 if grid[0][0] == 0 else 1))\n",
    "        while q:\n",
    "            x, y, dist = q.popleft()\n",
    "            if (x, y) in seen:\n",
    "                continue\n",
    "            if x == m - 1 and y == n -1:\n",
    "                return dist\n",
    "            seen[(x, y)] = dist\n",
    "            for di in dirs:\n",
    "                curx, cury = di[0] + x, di[1] + y\n",
    "                if 0 <= curx < m and 0 <= cury < n and (curx, cury) not in seen:\n",
    "                    if grid[curx][cury]:\n",
    "                        q.append((curx, cury, dist + 1))\n",
    "                    else:\n",
    "                        q.appendleft((curx, cury, dist))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # first method, Dijkstra\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        # seen = dict()\n",
    "        # q = []\n",
    "        # heapq.heappush(q, (0 if grid[0][0] == 0 else 1, 0, 0))\n",
    "        # while q:\n",
    "        #     dist, x, y = heapq.heappop(q)\n",
    "        #     if (x, y) in seen:\n",
    "        #         continue\n",
    "        #     if x == m - 1 and y == n - 1:\n",
    "        #         return dist\n",
    "        #     seen[(x, y)] = dist\n",
    "        #     for di in dirs:\n",
    "        #         curx, cury = di[0] + x, di[1] + y\n",
    "        #         if 0 <= curx < m and 0 <= cury < n and (curx, cury) not in seen:\n",
    "        #             heapq.heappush(q, (dist + (0 if grid[curx][cury] == 0 else 1), curx, cury))\n",
    "        \n",
    "        \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        dist = defaultdict(lambda :inf)\n",
    "        dist[(0,0)] = grid[0][0]\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        queue = deque([(0,0)])\n",
    "\n",
    "        while queue:\n",
    "            i , j = queue.popleft()\n",
    "            for di , dj in direction:\n",
    "                ni , nj = i + di , j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n:\n",
    "                    g = grid[ni][nj]\n",
    "                    if dist[(ni,nj)] > dist[(i,j)] + g:\n",
    "                        dist[(ni,nj)] = dist[(i,j)] + g\n",
    "                        if g == 0:\n",
    "                            queue.appendleft((ni,nj))\n",
    "                        else:\n",
    "                            queue.append((ni,nj))\n",
    "        return dist[(m-1,n-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        q = deque([(0, 0, 0)])\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        vis = set()\n",
    "        while q:\n",
    "            cnt, x, y = q.popleft()\n",
    "            if (x, y) in vis:\n",
    "                continue\n",
    "            vis.add((x, y))\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return cnt\n",
    "            for dx, dy in dirs:\n",
    "                a, b = x + dx, y + dy \n",
    "                if 0 <= a < m and 0 <= b < n:\n",
    "                    if grid[a][b] == 1:\n",
    "                        q.append((cnt+1, a, b))\n",
    "                    else:\n",
    "                        q.appendleft((cnt, a, b))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        r, c = len(grid), len(grid[0])\n",
    "        queue = collections.deque([(0,0,0)])\n",
    "        seen = set()\n",
    "        while queue:\n",
    "            i, j, step = queue.popleft()\n",
    "\n",
    "            if i == r - 1 and j == c - 1:\n",
    "                return step\n",
    "\n",
    "            if (i, j) in seen:\n",
    "                continue\n",
    "\n",
    "            seen.add((i, j))\n",
    "\n",
    "            for di, dj in [(1,0), (-1,0), (0,-1), (0,1)]:\n",
    "                newi, newj = i + di, j + dj\n",
    "                if 0 <= newi < r and 0 <= newj < c:\n",
    "                    if grid[newi][newj] == 0:\n",
    "                        queue.appendleft((newi, newj, step))\n",
    "                    else:\n",
    "                        queue.append((newi, newj, step + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        q = deque([(0, 0, 0)])\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = set()\n",
    "        while q:\n",
    "            i, j, k = q.popleft()\n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return k\n",
    "            if (i, j) in vis:\n",
    "                continue\n",
    "            vis.add((i, j))\n",
    "            for a, b in ((0, -1), (0, 1), (-1, 0), (1, 0)):\n",
    "                x, y = i + a, j + b\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if grid[x][y] == 0:\n",
    "                        q.appendleft((x, y, k))\n",
    "                    else:\n",
    "                        q.append((x, y, k + 1))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRECTIONS = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[0]*n for i in range(m)]\n",
    "        dp[0][0]=0\n",
    "        nex = deque()\n",
    "        step = 0\n",
    "        if grid[0][0]:\n",
    "            step=1\n",
    "        vis = set()\n",
    "        vis.add((0,0))\n",
    "        queue = deque([(0,0)])\n",
    "        while True:\n",
    "            while queue:\n",
    "                x,y = queue.popleft()\n",
    "                if x==m-1 and y==n-1:return step\n",
    "                for i in DIRECTIONS:\n",
    "                    x_new=x+i[0]\n",
    "                    y_new = y+i[1]\n",
    "                    if 0<=x_new<m and 0<=y_new<n and (x_new,y_new)not in vis:\n",
    "                        vis.add((x_new,y_new))\n",
    "                        if grid[x_new][y_new]:\n",
    "                            nex.append((x_new,y_new))\n",
    "                        else:\n",
    "                            queue.append((x_new,y_new))\n",
    "            queue = nex\n",
    "            nex = deque()\n",
    "            step+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "D4 = [(-1,0),(1,0),(0,-1),(0,1)] #迷宫的4个方向\n",
    "class Solution:\n",
    "    def minimumObstacles(self, G: List[List[int]]) -> int:\n",
    "        m,n = len(G),len(G[0])\n",
    "        def dijkstraF(e,s):\n",
    "            '''\n",
    "            输入：\n",
    "            e:邻接函数表\n",
    "            s:起点\n",
    "            返回：\n",
    "            dis:从s到每个顶点的最短路长度\n",
    "            '''\n",
    "            dis = defaultdict(lambda:float(\"inf\"))\n",
    "            dis[s] = 0\n",
    "            q = [(0,s)]\n",
    "            vis = set()\n",
    "            while q:\n",
    "                _, u = heapq.heappop(q)\n",
    "                if u in vis: continue\n",
    "                vis.add(u)\n",
    "                for v,w in e(u):\n",
    "                    if dis[v] > dis[u] + w:\n",
    "                        dis[v] = dis[u] + w\n",
    "                        heapq.heappush(q,(dis[v],v))\n",
    "            return dis\n",
    "        \n",
    "        def E(pos):\n",
    "            i,j=pos\n",
    "            for a,b in D4:\n",
    "                i2,j2 = i+a,j+b\n",
    "                if (0<=i2<m and 0<=j2<n):\n",
    "                    yield ((i2,j2),G[i2][j2])\n",
    "                    \n",
    "        dis = dijkstraF(E,(0,0))\n",
    "        return dis[(m-1,n-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n, cur, meet = len(grid), len(grid[0]), deque([[0, 0, 0]]), set()\n",
    "        def check(x, y): return 0 <= x < m and 0 <= y < n\n",
    "        end = (m-1, n-1)\n",
    "        while True:\n",
    "            c, i, j = cur.popleft()\n",
    "            if (i, j) in meet: continue\n",
    "            meet.add((i, j))\n",
    "            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if (x, y) == end: return c\n",
    "                if check(x, y):\n",
    "                    if grid[x][y]: cur.append([c+1, x, y])\n",
    "                    else: cur.appendleft([c, x, y])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        inf = math.inf\n",
    "        dist = [[inf for _ in range(n)]for _ in range(m)]\n",
    "        dist[0][0] = 0\n",
    "        seen = set()  # 已选的点\n",
    "        q = deque([(0, 0)])\n",
    "        while q:\n",
    "            r, l = q.popleft()\n",
    "            cur_dist=dist[r][l]\n",
    "            if (r, l) in seen:\n",
    "                continue\n",
    "            seen.add((r, l))\n",
    "            for nr, nl in [(r + 1, l), (r - 1, l), (r, l + 1), (r, l - 1)]:\n",
    "                if 0 <= nr < m and 0 <= nl < n and (nr, nl) not in seen:\n",
    "                    new_dist = cur_dist + grid[nr][nl]\n",
    "                    if new_dist < dist[nr][nl]:\n",
    "                        dist[nr][nl] = new_dist\n",
    "                        if grid[nr][nl]:\n",
    "                            q.append((nr, nl))\n",
    "                        else:\n",
    "                            q.appendleft((nr, nl))\n",
    "        return dist[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        que = [[0,0,0]]\n",
    "        visited = set()\n",
    "        while que:\n",
    "            cost,i,j = heapq.heappop(que)\n",
    "            if (i,j) in visited:\n",
    "                continue\n",
    "            visited.add((i,j))\n",
    "            if i==n-1 and j==m-1:\n",
    "                return cost\n",
    "            for i2,j2 in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                if 0<=i2<n and 0<=j2<m:\n",
    "                    heapq.heappush(que,[cost+grid[i][j],i2,j2])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        h, w = len(grid), len(grid[0])\n",
    "        dp = [[inf for _ in range(w)] for _ in range(h)]\n",
    "        dp[0][0] = 0\n",
    "        q = [[0, 0, 0]]\n",
    "        visited = set()\n",
    "        while q:\n",
    "            cost, i, j = heappop(q)\n",
    "            if (i, j) in visited:\n",
    "                continue\n",
    "            visited.add((i, j))\n",
    "            for di, dj in zip([-1, 1, 0, 0], [0, 0, -1, 1]):\n",
    "                ii = i + di\n",
    "                jj = j + dj\n",
    "                if ii < 0 or ii >= h or jj < 0 or jj >= w:\n",
    "                    continue\n",
    "                if dp[i][j] + grid[i][j] < dp[ii][jj]:\n",
    "                    dp[ii][jj] = dp[i][j] + grid[i][j]\n",
    "                    heappush(q, [dp[ii][jj], ii, jj])\n",
    "        return dp[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        self.grid, self.m, self.n = grid, len(grid), len(grid[0])\n",
    "        self.visited = defaultdict(bool)\n",
    "        self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        self.res = [[float('inf')] * self.n for _ in range(self.m)]\n",
    "        self.res[0][0] = 0 if self.grid[0][0] == 0 else 1\n",
    "        self.bfs(0, 0)\n",
    "        return self.res[-1][-1]\n",
    "    \n",
    "    def bfs(self, x, y):\n",
    "        queue = deque()\n",
    "        queue.append((x, y))\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            if self.visited[(x, y)]:\n",
    "                continue\n",
    "            self.visited[(x, y)] = True\n",
    "            for dx, dy in self.directions:\n",
    "                new_x, new_y = x+dx, y+dy\n",
    "                if 0 <= new_x < self.m and 0 <= new_y < self.n and not self.visited[(new_x, new_y)]:\n",
    "                    new_dic = self.res[x][y] + (0 if self.grid[new_x][new_y]==0 else 1)\n",
    "                    if new_dic < self.res[new_x][new_y]:\n",
    "                        self.res[new_x][new_y] = new_dic\n",
    "                        if self.grid[new_x][new_y] == 0:\n",
    "                            queue.appendleft((new_x, new_y))\n",
    "                        else:\n",
    "                            queue.append((new_x, new_y))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        self.grid, self.m, self.n = grid, len(grid), len(grid[0])\n",
    "        self.visited = defaultdict(bool)\n",
    "        self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        self.res = [[float('inf')] * self.n for _ in range(self.m)]\n",
    "        self.res[0][0] = 0 if self.grid[0][0] == 0 else 1\n",
    "        self.bfs(0, 0)\n",
    "        return self.res[-1][-1]\n",
    "    \n",
    "    def bfs(self, x, y):\n",
    "        queue = deque()\n",
    "        queue.append((x, y))\n",
    "        self.visited[(x, y)] = True\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            # if self.visited[(x, y)]:\n",
    "            #     continue\n",
    "            # self.visited[(x, y)] = True\n",
    "            for dx, dy in self.directions:\n",
    "                new_x, new_y = x+dx, y+dy\n",
    "                if 0 <= new_x < self.m and 0 <= new_y < self.n and not self.visited[(new_x, new_y)]:\n",
    "                    new_dic = self.res[x][y] + (0 if self.grid[new_x][new_y]==0 else 1)\n",
    "                    if new_dic < self.res[new_x][new_y]:\n",
    "                        self.res[new_x][new_y] = new_dic\n",
    "                        if self.grid[new_x][new_y] == 0:\n",
    "                            queue.appendleft((new_x, new_y))\n",
    "                            self.visited[(new_x, new_y)] = True\n",
    "                        else:\n",
    "                            queue.append((new_x, new_y))\n",
    "                            self.visited[(new_x, new_y)] = True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        # 利用双端队列维持单调递增，从而找到最小值\n",
    "        # self.grid, self.m, self.n = grid, len(grid), len(grid[0])\n",
    "        # self.visited = defaultdict(bool)\n",
    "        # self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        # self.res = [[float('inf')] * self.n for _ in range(self.m)]\n",
    "        # self.res[0][0] = 0 if self.grid[0][0] == 0 else 1\n",
    "        # self.bfs(0, 0)\n",
    "        # return self.res[-1][-1]\n",
    "\n",
    "        # dijkstra算法\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dist = [[float('inf')] * n for _ in range(m)]\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        visited = defaultdict(bool)\n",
    "        dist[0][0] = grid[0][0]\n",
    "        min_heap = [(dist[0][0], 0, 0)]\n",
    "        while min_heap:\n",
    "            cur_dist, x, y = heapq.heappop(min_heap)\n",
    "            if visited[(x, y)]:\n",
    "                continue\n",
    "            visited[(x, y)] = True\n",
    "            for dx, dy in directions:\n",
    "                new_x, new_y = x+dx, y+dy\n",
    "                if 0 <= new_x < m and 0 <= new_y < n:\n",
    "                    new_dist = cur_dist + grid[new_x][new_y]\n",
    "                    if new_dist < dist[new_x][new_y]:\n",
    "                        dist[new_x][new_y] = new_dist\n",
    "                        heapq.heappush(min_heap, (new_dist, new_x, new_y))\n",
    "        return dist[-1][-1]            \n",
    "    \n",
    "    def bfs(self, x, y):\n",
    "        queue = deque()\n",
    "        queue.append((x, y))\n",
    "        self.visited[(x, y)] = True\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            # if self.visited[(x, y)]:\n",
    "            #     continue\n",
    "            # self.visited[(x, y)] = True\n",
    "            for dx, dy in self.directions:\n",
    "                new_x, new_y = x+dx, y+dy\n",
    "                if 0 <= new_x < self.m and 0 <= new_y < self.n and not self.visited[(new_x, new_y)]:\n",
    "                    new_dic = self.res[x][y] + (0 if self.grid[new_x][new_y]==0 else 1)\n",
    "                    if new_dic < self.res[new_x][new_y]:\n",
    "                        self.res[new_x][new_y] = new_dic\n",
    "                        if self.grid[new_x][new_y] == 0:\n",
    "                            queue.appendleft((new_x, new_y))\n",
    "                            self.visited[(new_x, new_y)] = True\n",
    "                        else:\n",
    "                            queue.append((new_x, new_y))\n",
    "                            self.visited[(new_x, new_y)] = True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumObstacles(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        f = [[1000000]*m for _ in range(n)]\n",
    "        f[0][0] = 0\n",
    "        q = deque()\n",
    "        q.append((0,0))\n",
    "        vis = set()\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            for nx,ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if 0<=nx<n and 0<=ny<m and (nx,ny) not in vis:\n",
    "                    vis.add((nx,ny))\n",
    "                    if not grid[nx][ny]:\n",
    "                        f[nx][ny] = min(f[xx][yy] for xx,yy in [(nx+1,ny),(nx-1,ny),(nx,ny+1),(nx,ny-1)] if 0<=xx<n and 0<=yy<m)\n",
    "                        q.appendleft((nx,ny))\n",
    "                    else:\n",
    "                        f[nx][ny] = min(f[xx][yy] for xx,yy in [(nx+1,ny),(nx-1,ny),(nx,ny+1),(nx,ny-1)]if 0<=xx<n and 0<=yy<m)+1\n",
    "                        q.append((nx,ny)) \n",
    "        return f[n-1][m-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
